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 }
