首页 > 代码库 > BZOJ1845CQOI2005三角形面积并
BZOJ1845CQOI2005三角形面积并
1845: [Cqoi2005] 三角形面积并
Description
给出n个三角形,求它们并的面积。
Input
第一行为n(N < = 100), 即三角形的个数 以下n行,每行6个整数x1, y1, x2, y2, x3, y3,代表三角形的顶点坐标。坐标均为不超过10 ^ 6的实数,输入数据保留1位小数
Output
输出并的面积u, 保留两位小数
Sample Input
2
0.0 0.0 2.0 0.0 1.0 1.0
1.0 0.0 3.0 0.0 2.0 1.0
0.0 0.0 2.0 0.0 1.0 1.0
1.0 0.0 3.0 0.0 2.0 1.0
Sample Output
1.75
这道题是扫描线,第二点还卡精度,不过按照我的写法精度没问题。
思路简单,每条线求交点,过交点作y轴的平行线,切过去。
由于如果该点原本就是三角形的顶点,就会加入两个点到截线中,可以求相邻的截线的中位线,方便很多。
我看见网上很多程序都写了一堆operator,但是我没写还是过了OK!
好久没写码农题了。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int N=110; 7 const int eps=1e-8; 8 double x[9*N*N/2+3*N],y[3*N]; 9 bool re[9*N*N/2+3*N]; 10 struct node{ 11 double l,r,k,b; 12 bool upst; 13 }line[3*N]; 14 struct node1{ 15 double y; 16 int gr; 17 }; 18 int sl=0,sp=0; 19 inline void addline(int a,int b) 20 { 21 sl++; 22 line[sl].l=min(x[a],x[b]); 23 line[sl].r=max(x[a],x[b]); 24 if(x[a]==x[b]) 25 { 26 line[sl].upst=1; 27 return; 28 } 29 line[sl].k=(y[b]-y[a])/(x[b]-x[a]); 30 line[sl].b=y[a]-line[sl].k*x[a]; 31 } 32 inline void addpoint(int a,int b) 33 { 34 double X; 35 if(line[a].upst&&line[b].upst) return; 36 else if(line[a].upst) X=line[a].l; 37 else if(line[b].upst) X=line[b].l; 38 else X=(line[b].b-line[a].b)/(line[a].k-line[b].k); 39 if(max(line[a].l,line[b].l)<X&&X<min(line[a].r,line[b].r)) x[++sp]=X; 40 } 41 inline bool cmp(node1 u,node1 v) {return u.y<v.y;} 42 inline double cal(double x) 43 { 44 double res=0,la; 45 node1 cut[3*N]; 46 int sz=0,cnt=0; 47 bool used[N],flag=true; 48 memset(used,0,sizeof(used)); 49 for(int i=1;i<=sl;i++) if(line[i].l<=x&&x<=line[i].r) 50 { 51 cut[++sz].y=x*line[i].k+line[i].b; 52 cut[sz].gr=i/3; 53 if(i%3!=0) cut[sz].gr++; 54 } 55 sort(cut+1,cut+sz+1,cmp); 56 for(int i=1;i<=sz;i++) 57 { 58 if(used[cut[i].gr]) cnt--; 59 else 60 { 61 if(cnt==0) la=cut[i].y; 62 cnt++; 63 } 64 used[cut[i].gr]^=1; 65 if(cnt==0) res+=cut[i].y-la; 66 } 67 return res; 68 } 69 int main() 70 { 71 int n; 72 scanf("%d",&n); 73 sp=3*n; 74 for(int i=1;i<=n;i++) 75 { 76 for(int j=-2;j<=0;j++) scanf("%lf%lf",&x[i*3+j],&y[i*3+j]); 77 addline(3*i-2,3*i-1); 78 addline(3*i-1,3*i); 79 addline(3*i,3*i-2); 80 } 81 for(int i=1;i<sl;i++) 82 for(int j=i+1;j<=sl;j++) addpoint(i,j); 83 sort(x+1,x+sp+1); 84 double last=0.1410392,now,ans=0,lx; 85 for(int i=1;i<=sp;i++) 86 { 87 if(x[i]==last) re[i]=1; 88 else last=x[i]; 89 } 90 lx=x[1]; 91 for(int i=2;i<=sp;i++) if(!re[i]) 92 { 93 ans+=(x[i]-lx)*cal((x[i]+lx)/2); 94 lx=x[i]; 95 } 96 printf("%.2lf\n",ans-eps); 97 return 0; 98 }
BZOJ1845CQOI2005三角形面积并
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。