CSU 1812 三角形和矩形

湖南省第十二届大学生计算机程序设计竞赛$J$题

计算几何。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
char c = getchar();
x = ;
while(!isdigit(c)) c = getchar();
while(isdigit(c))
{
x = x * + c - '';
c = getchar();
}
} const int maxn=;
const int maxisn=; int dcmp(double x)
{
if(x>eps) return ;
return x<-eps ? - : ;
}
inline double Sqr(double x)
{
return x*x;
}
struct Point
{
double x,y;
Point()
{
x=y=;
}
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)==&&dcmp(a.y-b.y)==;
}
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<) return 0.0;
double s=p[].y*(p[n-].x-p[].x);
p[n]=p[];
for(int i=; i<n; i++)
{
s+=p[i].y*(p[i-].x-p[i+].x);
}
return fabs(s*0.5);
}
double CPIA(Point a[],Point b[],int na,int nb)
{
Point p[maxisn],temp[maxisn];
int i,j,tn,sflag,eflag;
a[na]=a[],b[nb]=b[];
memcpy(p,b,sizeof(Point)*(nb+));
for(i=; i<na&&nb>; ++i)
{
sflag=dcmp(a[i].cross(a[i+],p[]));
for(j=tn=; j<nb; ++j,sflag=eflag)
{
if(sflag>=) temp[tn++]=p[j];
eflag=dcmp(a[i].cross(a[i+],p[j+]));
if((sflag^eflag)==-)
temp[tn++]=LineCross(a[i],a[i+],p[j],p[j+]);
}
memcpy(p,temp,sizeof(Point)*tn);
nb=tn,p[nb]=p[];
}
if(nb<) return 0.0;
return PolygonArea(p,nb);
}
double SPIA(Point a[],Point b[],int na,int nb)
{
int i,j;
Point t1[],t2[];
double res=0.0,if_clock_t1,if_clock_t2;
a[na]=t1[]=a[];
b[nb]=t2[]=b[];
for(i=; i<na; i++)
{
t1[]=a[i-],t1[]=a[i];
if_clock_t1=dcmp(t1[].cross(t1[],t1[]));
if(if_clock_t1<) swap(t1[],t1[]);
for(j=; j<nb; j++)
{
t2[]=b[j-],t2[]=b[j];
if_clock_t2=dcmp(t2[].cross(t2[],t2[]));
if(if_clock_t2<) swap(t2[],t2[]);
res+=CPIA(t1,t2,,)*if_clock_t1*if_clock_t2;
}
}
return res;
} Point a[],b[];
Point aa[],bb[]; int main()
{
int n1,n2;
double x1,y1,x2,y2,x3,y3,x4,y4;
while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4))
{
n1=,n2=;
a[].x=x1; a[].y=y1;
a[].x=x1; a[].y=y2;
a[].x=x2; a[].y=y1; b[].x=x3; b[].y=y3;
b[].x=x3; b[].y=y4;
b[].x=x4; b[].y=y4;
b[].x=x4; b[].y=y3; printf("%.6lf\n",abs(SPIA(a,b,n1,n2)));
}
return ;
}
上一篇:xml之XSLT


下一篇:计算几何板子题【2019牛客国庆集训派对day7——三角形和矩形】【多边形相交的面积】