「BZOJ2618」[CQOI2006] 凸多边形
Description
逆时针给出n个凸多边形的顶点坐标，求它们交的面积。例如n=2时，两个凸多边形如下图：
则相交部分的面积为5.233。
Input
第一行有一个整数n，表示凸多边形的个数，以下依次描述各个多边形。第i个多边形的第一行包含一个整数mi，表示多边形的边数，以下mi行每行两个整数，逆时针给出各个顶点的坐标。
Output
输出文件仅包含一个实数，表示相交部分的面积，保留三位小数。
Sample Input
2
6
-2 0
-1 -2
1 -2
2 0
1 2
-1 2
4
0 -3
1 -1
2 2
-1 0
Sample Output
5.233
HINT
100%的数据满足：2<=n<=10，3<=mi<=50，每维坐标为[-1000,1000]内的整数
题解
我只会用半平面交瞎搞
题目直接等价于几百条直线求半平面交面积
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include<cstdio> #include<algorithm> #include<cmath> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,cnt,tot; double ans; struct P{double x,y;}p[1005],a[1005]; struct L{P a,b;double slop;}l[1005],q[1005]; P operator-(P a,P b) { P t;t.x=a.x-b.x;t.y=a.y-b.y;return t; } double operator*(P a,P b) { return a.x*b.y-a.y*b.x; } bool operator<(L a,L b) { if(a.slop!=b.slop)return a.slop<b.slop; return (a.b-a.a)*(b.b-a.a)>0; } P inter(L a,L b) { double k1,k2,t; k1=(b.b-a.a)*(a.b-a.a); k2=(a.b-a.a)*(b.a-a.a); t=k1/(k1+k2); P ans; ans.x=b.b.x+(b.a.x-b.b.x)*t; ans.y=b.b.y+(b.a.y-b.b.y)*t; return ans; } bool jud(L a,L b,L t) { P p=inter(a,b); return (t.b-t.a)*(p-t.a)<0; } void hpi() { sort(l+1,l+cnt+1); // for(int i=1;i<=cnt;i++) // cout<<l[i].a.x<<' '<<l[i].a.y<<' '<<l[i].b.x<<' '<<l[i].b.y<<endl; int L=1,R=0;tot=0; for(int i=1;i<=cnt;i++) { if(l[i].slop!=l[i-1].slop)tot++; l[tot]=l[i]; } cnt=tot;tot=0; q[++R]=l[1];q[++R]=l[2]; for(int i=3;i<=cnt;i++) { while(L<R&&jud(q[R-1],q[R],l[i]))R--; while(L<R&&jud(q[L+1],q[L],l[i]))L++; q[++R]=l[i]; } while(L<R&&jud(q[R-1],q[R],q[L]))R--; while(L<R&&jud(q[L+1],q[L],q[R]))L++; q[R+1]=q[L]; for(int i=L;i<=R;i++) a[++tot]=inter(q[i],q[i+1]); } void getans() { if(tot<3)return; a[++tot]=a[1]; for(int i=1;i<=tot;i++) ans+=a[i]*a[i+1]; ans=fabs(ans)/2; } int main() { n=read(); for(int i=1;i<=n;i++) { int k=read(); for(int j=1;j<=k;j++) p[j].x=read(),p[j].y=read(); p[k+1]=p[1]; for(int j=1;j<=k;j++) l[++cnt].a=p[j],l[cnt].b=p[j+1]; } for(int i=1;i<=cnt;i++) l[i].slop=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x); hpi(); getans(); printf("%.3lf",ans); return 0; } |
计数器 9301923
OI 课件=>
OI 课件=>
Orz