2014-07-30

http://acm.hdu.edu.cn/showproblem.php?pid=2528
解题思路：
　　求多边形被一条直线分成两部分的面积分别是多少。因为题目给的直线一定能把多边形分成两部分，所以就不用考虑多边形是否与直线相交。直接求问题。
　　
　　将多边形的每一条边与直线判断是否相交。若相交，就从这点开始计算面积，直到判断到下一个边与直线相交的点。这之间的面积求出来为area2。
　　area1为多边形的总面积。多边形被直线分成的另外一部分面积 = area1 - area2

　　有一个特殊的情况：当直线与多边形的顶点相交时，应该考虑下如何处理

  1 #include<cmath>  2 #include<cstdio>  3 #include<iostream>  4 #include<algorithm>  5 using namespace std;  6   7 #define MAXN 30  8 #define EPS 0.00000001  9  10 int dcmp(double x){ 11     if(fabs(x) < EPS) 12         return 0; 13     return x < 0 ? -1 : 1; 14 } 15  16 struct Point{ 17     double x, y; 18     Point(double x = 0, double y = 0): x(x), y(y) {} 19  20     bool operator != (const Point & other){ 21         return dcmp(x - other.x) != 0 || (dcmp(x - other.x) == 0 && dcmp(y - other.y) != 0); 22     } 23 }; 24  25 struct Line{ 26     Point A, B; 27     //Line(Point A = Point(0, 0), Point B = Point(0, 0)): A(A), B(B){} 28 }; 29  30 typedef Point Vector; 31  32 Vector operator + (Vector A, Vector B){ 33     return Vector(A.x + B.x, A.y + B.y); 34 } 35  36 Vector operator - (Point A, Point B){ 37     return Vector(A.x - B.x, A.y - B.y); 38 } 39  40 Vector operator * (Vector A, double d){ 41     return Vector(A.x * d, A.y * d); 42 } 43  44 Vector operator / (Vector A, double d){ 45     return Vector(A.x / d, A.y / d); 46 } 47  48 double dot(Vector A, Vector B){//点乘 49     return A.x * B.x + A.y * B.y; 50 } 51  52 double cross(Vector A, Vector B){//叉乘 53     return A.x * B.y - A.y * B.x; 54 } 55  56 int n; 57 Point p[MAXN]; 58 Line line; 59  60 bool input(){ 61     scanf("%d", &n ); 62     if(!n){ 63         return false; 64     } 65     for(int i = 0; i < n; i++ ){ 66         scanf("%lf%lf", &p[i].x, &p[i].y ); 67     } 68     scanf("%lf%lf%lf%lf", &line.A.x, &line.A.y, &line.B.x, &line.B.y ); 69     return true; 70 } 71  72 double polygon_area(){//求多边形面积 73     double area = 0; 74     for(int i = 1; i < n - 1; i++ ){ 75         area += cross(p[i] - p[0], p[i + 1] - p[0]); 76     } 77     return fabs(area) * 0.5; 78 } 79  80 bool line_segment_intersect(Line L, Point A, Point B, Point &P){//直线和线段相交 81     Vector a = A - L.B, b = L.A - L.B, c = B - L.B; 82     if(dcmp(cross(a, b)) * dcmp(cross(b, c)) >= 0){//若直线和线段相交 求出交点 《算法入门经典训练之南》上的公式 83         Vector u = L.A - A; 84         double t = cross(A - B, u) / cross(b, A - B); 85         P = L.A + b * t; 86         return true; 87     } 88     return false; 89 } 90  91 void solve(){ 92     int flag = 0; 93     double area1 = polygon_area(), area2 = 0;//area1算出多边形总面积 94     Point P, T; 95  96     p[n] = p[0]; 97     for(int i = 0; i < n; i++ ){ 98         if(flag == 0 && line_segment_intersect(line, p[i], p[i + 1], P)){//第一次相交点 99             area2 += cross(P, p[i + 1]);100             flag++;101         }else if(flag == 1 && line_segment_intersect(line, p[i], p[i + 1], T) && P != T){//第二次相交点102             area2 += cross(p[i], T);103             area2 += cross(T, P);104             flag++;105             break;106         }else if(flag == 1){107             area2 += cross(p[i], p[i + 1]);108         }109     }110     area2 = fabs(area2) * 0.5;111     area1 -= area2;//area1 获取多边形另外一半的面积112     if(area1 < area2){//规定大面积在前面 输出113         swap(area1, area2);114     }115     printf("%.0lf %.0lf\n", area1, area2);116 }117 118 int main(){119     //freopen("data.in", "r", stdin );120     while(input()){121         solve();122     }123     return 0;124 }