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

链接：https://ac.nowcoder.com/acm/contest/1112/J
来源：牛客网

题目描述

Bobo 有一个三角形和一个矩形，他想求他们交的面积。
具体地，三角形和矩形由 8 个整数 x1,y1,x2,y2,x3,y3,x4,y4x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4x1?,y1?,x2?,y2?,x3?,y3?,x4?,y4? 描述。
表示三角形的顶点坐标是 (x1,y1),(x1,y2),(x2,y1)(x_1, y_1), (x_1, y_2), (x_2, y_1)(x1?,y1?),(x1?,y2?),(x2?,y1?)，
矩形的顶点坐标是 (x3,y3),(x3,y4),(x4,y4),(x4,y3)(x_3, y_3), (x_3, y_4), (x_4, y_4), (x_4, y_3)(x3?,y3?),(x3?,y4?),(x4?,y4?),(x4?,y3?).

输入描述:

输入包含不超过 30000 组数据。
每组数据的第一行包含 4 个整数 x1,y1,x2,y2x_1, y_1, x_2, y_2x1?,y1?,x2?,y2? (x1≠x2,y1≠y2x_1 \neq x_2, y_1 \neq y_2x1??=x2?,y1??=y2?).
第二行包含 4 个整数 x3,y3,x4,y4x_3, y_3, x_4, y_4x3?,y3?,x4?,y4? (x3x3?<x4?,y3?<y4?).
(0≤xi,yi≤1040 \leq x_i, y_i \leq 10^40≤xi?,yi?≤104)

输出描述:

对于每组数据，输出一个实数表示交的面积。绝对误差或相对误差小于 10?610^{-6}10?6 即认为正确。

示例1

输入

复制

1 1 3 3
0 0 2 2

输出

复制

1.00000000

示例2

输入

复制

0 3 3 1
0 0 2 2

输出

复制

0.75000000

示例3

输入

复制

4462 1420 2060 2969
4159 257 8787 2970

输出

复制

439744.13967527
AC代码：

  1 /* 
  2  * 多边形的交，多边形的边一定是要按逆时针方向给出 
  3  * 还要判断是凸包还是凹包，调用相应的函数 
  4  * 面积并，只要和面积减去交即可 
  5  */  
  6 #include   
  7 using namespace std;  
  8   
  9 const int maxn = 300;  
 10 const double eps = 1e-8;  
 11 int dcmp(double x)  
 12 {  
 13     if(x > eps) return 1;  
 14     return x < -eps ? -1 : 0;  
 15 }  
 16 struct Point  
 17 {  
 18     double x, y;  
 19 };  
 20 double cross(Point a,Point b,Point c) ///叉积  
 21 {  
 22     return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);  
 23 }  
 24 Point intersection(Point a,Point b,Point c,Point d)  
 25 {  
 26     Point p = a;  
 27     double t =((a.x-c.x)*(c.y-d.y)-(a.y-c.y)*(c.x-d.x))/((a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x));  
 28     p.x +=(b.x-a.x)*t;  
 29     p.y +=(b.y-a.y)*t;  
 30     return p;  
 31 }  
 32 //计算多边形面积  
 33 double PolygonArea(Point p[], int n)  
 34 {  
 35     if(n < 3) return 0.0;  
 36     double s = p[0].y * (p[n - 1].x - p[1].x);  
 37     p[n] = p[0];  
 38     for(int i = 1; i < n; ++ i)  
 39         s += p[i].y * (p[i - 1].x - p[i + 1].x);  
 40     return fabs(s * 0.5);  
 41 }  
 42 double CPIA(Point a[], Point b[], int na, int nb)//ConvexPolygonIntersectArea  
 43 {  
 44     Point p[20], tmp[20];  
 45     int tn, sflag, eflag;  
 46     a[na] = a[0], b[nb] = b[0];  
 47     memcpy(p,b,sizeof(Point)*(nb + 1));  
 48     for(int i = 0; i < na && nb > 2; i++)  
 49     {  
 50         sflag = dcmp(cross(a[i + 1], p[0],a[i]));  
 51         for(int j = tn = 0; j < nb; j++, sflag = eflag)  
 52         {  
 53             if(sflag>=0) tmp[tn++] = p[j];  
 54             eflag = dcmp(cross(a[i + 1], p[j + 1],a[i]));  
 55             if((sflag ^ eflag) == -2)  
 56                 tmp[tn++] = intersection(a[i], a[i + 1], p[j], p[j + 1]); ///求交点  
 57         }  
 58         memcpy(p, tmp, sizeof(Point) * tn);  
 59         nb = tn, p[nb] = p[0];  
 60     }  
 61     if(nb < 3) return 0.0;  
 62     return PolygonArea(p, nb);  
 63 }  
 64 double SPIA(Point a[], Point b[], int na, int nb)///SimplePolygonIntersectArea 调用此函数  
 65 {  
 66     int i, j;  
 67     Point t1[4], t2[4];  
 68     double res = 0, num1, num2;  
 69     a[na] = t1[0] = a[0], b[nb] = t2[0] = b[0];  
 70     for(i = 2; i < na; i++)  
 71     {  
 72         t1[1] = a[i-1], t1[2] = a[i];  
 73         num1 = dcmp(cross(t1[1], t1[2],t1[0]));  
 74         if(num1 < 0) swap(t1[1], t1[2]);  
 75         for(j = 2; j < nb; j++)  
 76         {  
 77             t2[1] = b[j - 1], t2[2] = b[j];  
 78             num2 = dcmp(cross(t2[1], t2[2],t2[0]));  
 79             if(num2 < 0) swap(t2[1], t2[2]);  
 80             res += CPIA(t1, t2, 3, 3) * num1 * num2;  
 81         }  
 82     }  
 83    // res=fabs(res);
 84     return res;  
 85 }  
 86 Point p1[maxn], p2[maxn];  
 87 int n1, n2;  
 88 int main()  
 89 {  
 90            int x1,x2,x3,x4,y1,y2,y3,y4;
 91        while(~    scanf("%d %d %d %d",&x1,&y1,&x2,&y2)){
 92            
 93        
 94            scanf("%d %d %d %d",&x3,&y3,&x4,&y4);
 95               p1[0].x = x1;p1[0].y = y1;
 96         p1[1].x = x1;p1[1].y = y2;
 97         p1[2].x = x2;p1[2].y = y1;
 98 
 99         p2[0].x = x3;p2[0].y = y3;
100         p2[1].x = x3;p2[1].y = y4;
101         p2[2].x = x4;p2[2].y = y4;
102         p2[3].x = x4;p2[3].y = y3;
103          double s1 = SPIA(p1,p2,3,4);
104         printf("%.8f\n",fabs(s1));
105     }
106     return 0;  
107 }