【BZOJ2618】[CQOI2006]凸多边形(半平面交)

【BZOJ2618】[CQOI2006]凸多边形(半平面交)

题面

BZOJ

洛谷

题解

这个东西就是要求凸多边形的边所形成的半平面交。

那么就是一个半平面交模板题了。

这里写的是平方的做法。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 10010
#define inf 1000
#define double long double
const double eps=0;
struct Point{double x,y,ang;};
bool operator<(Point a,Point b){return (a.ang!=b.ang)?a.ang<b.ang:a.x<b.x;}
Point operator+(Point a,Point b){return (Point){a.x+b.x,a.y+b.y};}
Point operator-(Point a,Point b){return (Point){a.x-b.x,a.y-b.y};}
Point operator*(Point a,double b){return (Point){a.x*b,a.y*b};}
Point operator/(Point a,double b){return (Point){a.x/b,a.y/b};}
double operator*(Point a,Point b){return a.x*b.x+a.y*b.y;}
double Cross(Point a,Point b){return a.x*b.y-a.y*b.x;}
double Len(Point a){return sqrt(a.x*a.x+a.y*a.y);}
double Dis(Point a,Point b){return Len(a-b);}
Point Rotate(Point p,double a){double c=cos(a),s=sin(a);return (Point){p.x*c-p.y*s,p.x*s+p.y*c};}
struct Line{Point a,v;};
Point S[MAX],tmp[MAX];int top;
Point Intersection(Line a,Line b)
{
Point c=b.a-a.a;
double t=Cross(b.v,c)/Cross(b.v,a.v);
return a.a+a.v*t;
}
void pre()
{
top=0;
S[++top]=(Point){inf,inf};
S[++top]=(Point){-inf,inf};
S[++top]=(Point){-inf,-inf};
S[++top]=(Point){inf,-inf};
}
void Cut(Line a)
{
S[top+1]=S[1];int tot=0;
for(int i=1;i<=top;++i)
{
double v1=Cross(a.v,S[i]-a.a);
double v2=Cross(a.v,S[i+1]-a.a);
if(v1>=0)tmp[++tot]=S[i];
if(v1*v2<0)tmp[++tot]=Intersection(a,(Line){S[i],S[i+1]-S[i]});
}
top=tot;for(int i=1;i<=top;++i)S[i]=tmp[i];
}
int n;Point p[MAX];
int main()
{
int T;scanf("%d",&T);pre();
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%Lf%Lf",&p[i].x,&p[i].y);
for(int i=1;i<=n;++i)p[i].x+=eps;
p[n+1]=p[1];
for(int i=1;i<=n;++i)Cut((Line){p[i],p[i+1]-p[i]});
continue;
}
double ans=0;S[top+1]=S[1];
for(int i=2;i<=top;++i)ans+=Cross(S[i]-S[1],S[i+1]-S[1]);
printf("%.3Lf\n",ans/2);
}
上一篇:Zookeeper配置文件


下一篇:Why my setting does not work?