本文共 7491 字，大约阅读时间需要 24 分钟。
题意：没看懂= =
sol：在纸上随便画两下就可以看出，答案即按逆时针方向建立line，求它们的半平面交的面积。
模板题。注意输出答案时输出ans+eps，否则可能会出现结果为-0.00的情况。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #include 25 #include 26 #include 27 #include 28 #define mp make_pair 29 #define pb push_back 30 using namespace std; 31 const double eps=1e-6; 32 const double pi=acos(-1.0); 33 const double inf=1e20; 34 const int maxp=1111; 35 int dblcmp(double d) 36 { 37 if (fabs(d) eps?1:-1; 39 } 40 inline double sqr(double x){ return x*x;} 41 struct point 42 { 43 double x,y; 44 point(){} 45 point(double _x,double _y): 46 x(_x),y(_y){}; 47 void input() 48 { 49 scanf("%lf%lf",&x,&y); 50 } 51 void output() 52 { 53 printf("%.2f %.2f\n",x,y); 54 } 55 bool operator==(point a)const 56 { 57 return dblcmp(a.x-x)==0&&dblcmp(a.y-y)==0; 58 } 59 bool operator<(point a)const 60 { 61 return dblcmp(a.x-x)==0?dblcmp(y-a.y)<0:x sub(p);122 double c=cos(angle),s=sin(angle);123 return point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);124 }125 };126 struct line127 {128 point a,b;129 line(){}130 line(point _a,point _b)131 {132 a=_a;133 b=_b;134 }135 bool operator==(line v)136 {137 return (a==v.a)&&(b==v.b);138 }139 //倾斜角angle140 line(point p,double angle)141 {142 a=p;143 if (dblcmp(angle-pi/2)==0)144 {145 b=a.add(point(0,1));146 }147 else148 {149 b=a.add(point(1,tan(angle)));150 }151 }152 //ax+by+c=0153 line(double _a,double _b,double _c)154 {155 if (dblcmp(_a)==0)156 {157 a=point(0,-_c/_b);158 b=point(1,-_c/_b);159 }160 else if (dblcmp(_b)==0)161 {162 a=point(-_c/_a,0);163 b=point(-_c/_a,1);164 }165 else166 {167 a=point(0,-_c/_b);168 b=point(1,(-_c-_a)/_b);169 }170 }171 void input()172 {173 a.input();174 b.input();175 }176 void adjust()177 {178 if (b 0)return 2;200 return 3;201 }202 bool pointonseg(point p)203 {204 return dblcmp(p.sub(a).det(b.sub(a)))==0&&dblcmp(p.sub(a).dot(p.sub(b)))<=0;205 }206 bool parallel(line v)207 {208 return dblcmp(b.sub(a).det(v.b.sub(v.a)))==0;209 }210 //2 规范相交211 //1 非规范相交212 //0 不相交213 int segcrossseg(line v)214 {215 int d1=dblcmp(b.sub(a).det(v.a.sub(a)));216 int d2=dblcmp(b.sub(a).det(v.b.sub(a)));217 int d3=dblcmp(v.b.sub(v.a).det(a.sub(v.a)));218 int d4=dblcmp(v.b.sub(v.a).det(b.sub(v.a)));219 if ((d1^d2)==-2&&(d3^d4)==-2)return 2;220 return (d1==0&&dblcmp(v.a.sub(a).dot(v.a.sub(b)))<=0||221 d2==0&&dblcmp(v.b.sub(a).dot(v.b.sub(b)))<=0||222 d3==0&&dblcmp(a.sub(v.a).dot(a.sub(v.b)))<=0||223 d4==0&&dblcmp(b.sub(v.a).dot(b.sub(v.b)))<=0);224 }225 int linecrossseg(line v)//*this seg v line226 {227 int d1=dblcmp(b.sub(a).det(v.a.sub(a)));228 int d2=dblcmp(b.sub(a).det(v.b.sub(a)));229 if ((d1^d2)==-2)return 2;230 return (d1==0||d2==0);231 }232 //0 平行233 //1 重合234 //2 相交235 int linecrossline(line v)236 {237 if ((*this).parallel(v))238 {239 return v.relation(a)==3;240 }241 return 2;242 }243 point crosspoint(line v)244 {245 double a1=v.b.sub(v.a).det(a.sub(v.a));246 double a2=v.b.sub(v.a).det(b.sub(v.a));247 return point((a.x*a2-b.x*a1)/(a2-a1),(a.y*a2-b.y*a1)/(a2-a1));248 }249 double dispointtoline(point p)250 {251 return fabs(p.sub(a).det(b.sub(a)))/length();252 }253 double dispointtoseg(point p)254 {255 if (dblcmp(p.sub(b).dot(a.sub(b)))<0||dblcmp(p.sub(a).dot(b.sub(a)))<0)256 {257 return min(p.distance(a),p.distance(b));258 }259 return dispointtoline(p);260 }261 point lineprog(point p)262 {263 return a.add(b.sub(a).mul(b.sub(a).dot(p.sub(a))/b.sub(a).len2()));264 }265 point symmetrypoint(point p)266 {267 point q=lineprog(p);268 return point(2*q.x-p.x,2*q.y-p.y);269 }270 };271 272 struct Vector:public point273 {274 Vector(){}275 Vector(double a,double b)276 {277 x=a; y=b;278 }279 Vector(point _a,point _b) //a->b280 {281 double dx=_b.x-_a.x;282 double dy=_b.y-_a.y;283 x=dx; y=dy;284 }285 Vector(line v)286 {287 double dx=v.b.x-v.a.x;288 double dy=v.b.y-v.a.y;289 x=dx; y=dy;290 }291 double length()292 {293 return (sqrt(x*x+y*y));294 }295 Vector Normal()296 {297 double L=sqrt(x*x+y*y);298 Vector Vans=Vector(-y/L,x/L);299 return Vans;300 }301 };302 303 struct halfplane:public line //半平面304 {305 double angle;306 halfplane(){}307 //表示向量 a->b逆时针(左侧)的半平面308 halfplane(point _a,point _b)309 {310 a=_a;311 b=_b;312 }313 halfplane(line v)314 {315 a=v.a;316 b=v.b;317 }318 void calcangle()319 {320 angle=atan2(b.y-a.y,b.x-a.x);321 }322 bool operator<(const halfplane &b)const323 {324 return angle 0;365 }366 };367 void norm()368 {369 point mi=p[0];370 for (int i=1;i =0;i--)394 {395 while (top!=temp&&convex.p[top].sub(p[i]).det(convex.p[top-1].sub(p[i]))<=0)396 top--;397 convex.p[++top]=p[i];398 }399 }400 bool isconvex()401 {402 bool s[3];403 memset(s,0,sizeof(s));404 int i,j,k;405 for (i=0;i 0&&u<0&&v>=0)cnt++;438 if (k<0&&v<0&&u>=0)cnt--;439 }440 return cnt!=0;441 }442 //1 在多边形内长度为正443 //2 相交或与边平行444 //0 无任何交点445 int relationline(line u)446 {447 int i,j,k=0;448 getline();449 for (i=0;i vp;456 for (i=0;i =0)po.p[top++]=p[i];492 if (d1*d2<0)po.p[top++]=u.crosspoint(line(p[i],p[(i+1)%n]));493 }494 }495 double getcircumference()496 {497 double sum=0;498 int i;499 for (i=0;i 0)return 1;524 return 0;525 }526 point getbarycentre()527 {528 point ret(0,0);529 double area=0;530 int i;531 for (i=1;i =0)558 {559 ans+=c.areatriangle(p[i],p[j]);560 }561 else562 {563 ans-=c.areatriangle(p[i],p[j]);564 }565 }566 return fabs(ans);567 }568 //多边形和圆关系569 //0 一部分在圆外570 //1 与圆某条边相切571 //2 完全在圆内572 int relationcircle(circle c)573 {574 getline();575 int i,x=2;576 if (relationpoint(c.p)!=1)return 0;577 for (i=0;i 0)611 {612 tri[st]=p[i];613 solve(i,st+1,tri,c);614 }615 }616 }617 circle mincircle()//点集最小圆覆盖618 {619 random_shuffle(p,p+n);620 point tri[4];621 circle c;622 solve(n,0,tri,c);623 return c;624 }625 int circlecover(double r)//单位圆覆盖626 {627 int ans=0,i,j;628 vector >v;629 for (i=0;i >1;669 if (dblcmp(q.sub(p[0]).det(p[mid].sub(p[0])))>=0&&dblcmp(q.sub(p[0]).det(p[mid+1].sub(p[0])))<0)670 {671 polygon c;672 c.p[0]=p[mid];673 c.p[1]=p[mid+1];674 c.p[2]=p[0];675 c.n=3;676 if (c.relationpoint(q))return mid;677 return -1;678 }679 if (dblcmp(q.sub(p[0]).det(p[mid].sub(p[0])))>0)680 {681 low=mid+1;682 }683 else684 {685 high=mid-1;686 }687 }688 return -1;689 }690 };691 692 struct halfplanes //半平面交693 {694 int n;695 halfplane hp[maxp];696 point p[maxp];697 int que[maxp];698 int st,ed;699 void push(halfplane tmp)700 {701 hp[n++]=tmp;702 }703 void unique()704 {705 int m=1,i;706 for (i=1;i 0))hp[m-1]=hp[i];710 }711 n=m;712 }713 bool halfplaneinsert()714 {715 int i;716 for (i=0;i =ed)return false;733 return true;734 }735 void getconvex(polygon &con)736 {737 p[st]=hp[que[st]].crosspoint(hp[que[ed]]);738 con.n=ed-st+1;739 int j=st,i=0;740 for (;j<=ed;i++,j++)741 {742 con.p[i]=p[j];743 }744 }745 };746 747 point p[2000];748 halfplanes TH;749 int n,T;750 751 int main()752 {753 //freopen("in.txt","r",stdin);754 755 cin>>T;756 while (T--)757 {758 cin>>n;759 for (int i=n-1;i>=0;i--)760 p[i].input();761 //p[i]->p[i+1]762 763 TH.n=0;764 for (int i=0;i<=n-1;i++)765 TH.push(halfplane(p[i],p[(i+1)%n]));766 767 double ans=0.00;768 if (TH.halfplaneinsert())769 {770 polygon Gans;771 TH.getconvex(Gans);772 ans=Gans.getarea();773 }774 printf("%.2lf\n",ans+eps);775 }776 777 return 0;778 }
转载于:https://www.cnblogs.com/pdev/p/4277747.html
