本文共 2448 字，大约阅读时间需要 8 分钟。
湖南省第十二届大学生计算机程序设计竞赛$J$题
计算几何。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template inline void read(T &x){ char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }}const int maxn=555;const int maxisn=10;int dcmp(double x){ if(x>eps) return 1; return x<-eps ? -1 : 0;}inline double Sqr(double x){ return x*x;}struct Point{ double x,y; Point() { x=y=0; } Point(double x,double y):x(x),y(y) {}; friend Point operator + (const Point &a,const Point &b) { return Point(a.x+b.x,a.y+b.y); } friend Point operator - (const Point &a,const Point &b) { return Point(a.x-b.x,a.y-b.y); } friend bool operator == (const Point &a,const Point &b) { return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0; } friend Point operator * (const Point &a,const double &b) { return Point(a.x*b,a.y*b); } friend Point operator * (const double &a,const Point &b) { return Point(a*b.x,a*b.y); } friend Point operator / (const Point &a,const double &b) { return Point(a.x/b,a.y/b); } friend bool operator < (const Point &a, const Point &b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } inline double dot(const Point &b)const { return x*b.x+y*b.y; } inline double cross(const Point &b,const Point &c)const { return (b.x-x)*(c.y-y)-(c.x-x)*(b.y-y); }};Point LineCross(const Point &a,const Point &b,const Point &c,const Point &d){ double u=a.cross(b,c),v=b.cross(a,d); return Point((c.x*v+d.x*u)/(u+v),(c.y*v+d.y*u)/(u+v));}double PolygonArea(Point p[],int n){ if(n<3) return 0.0; double s=p[0].y*(p[n-1].x-p[1].x); p[n]=p[0]; for(int i=1; i 2; ++i) { sflag=dcmp(a[i].cross(a[i+1],p[0])); for(j=tn=0; j =0) temp[tn++]=p[j]; eflag=dcmp(a[i].cross(a[i+1],p[j+1])); if((sflag^eflag)==-2) temp[tn++]=LineCross(a[i],a[i+1],p[j],p[j+1]); } memcpy(p,temp,sizeof(Point)*tn); nb=tn,p[nb]=p[0]; } if(nb<3) return 0.0; return PolygonArea(p,nb);}double SPIA(Point a[],Point b[],int na,int nb){ int i,j; Point t1[4],t2[4]; double res=0.0,if_clock_t1,if_clock_t2; a[na]=t1[0]=a[0]; b[nb]=t2[0]=b[0]; for(i=2; i
转载于:https://www.cnblogs.com/zufezzt/p/5838163.html