poj2451

题意：给定一些半平面，求面积。。
直接套用模板。。
code：
  1 /*
  2   Time:2013-04-11 19:09:39
  3   State:Accepted
  4 */
  5 #include<iostream>
  6 #include<cstring>
  7 #include<cstdio>
  8 #include<cmath>
  9 #include<algorithm>
 10 #include<set>
 11 #define eps  1e-8
 12 #define maxn  25010
 13 using namespace std;
 14 
 15 int ln, q[maxn], top,  bot, n, ord[maxn];
 16 
 17 struct point{double x, y; } p[maxn];
 18 struct line { 
 19              point a, b; 
 20              double angle; 
 21 } l[maxn];
 22 
 23 void add_line(double x1, double y1, double x2, double y2 ){
 24      l[ln].a.x = x1;
 25      l[ln].b.x = x2;
 26      l[ln].a.y = y1;
 27      l[ln].b.y = y2;
 28      l[ln].angle = atan2(y2 - y1, x2 - x1);  
 29      ord[ln] = ln;
 30      ++ln;
 31 }
 32 
 33 void init(){
 34     double x1 , y1, x2, y2;
 35     while (scanf("%d", &n) != EOF){
 36         for (int i = ln = 0;  i < n; ++i){
 37             scanf("%lf%lf%lf%lf",&x1, &y1, &x2, &y2);
 38             add_line(x1 , y1, x2, y2);    
 39         }      
 40     }
 41     add_line(0,0,10000,0);
 42     add_line(10000,0,10000,10000);
 43     add_line(10000,10000,0,10000);
 44     add_line(0,10000,0,0);
 45 }
 46 
 47 int dblcmp(double k){
 48     if (fabs(k) < eps) return 0;
 49     return k > 0 ? 1 : -1;
 50 }
 51 
 52 double multi(point p0, point p1, point p2){
 53     return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);    
 54 }
 55 
 56 bool cmp(const int u, const int v){
 57      int d = dblcmp(l[u].angle - l[v].angle);
 58      if (d == 0) return dblcmp(multi(l[u].a, l[v].a,l[v].b)) > 0;
 59      return d < 0;
 60 }
 61 
 62 void get_point(line l1, line l2, point& p){
 63      double  dot1,  dot2;
 64      dot1 = multi(l2.a, l1.b, l1.a);
 65      dot2 = multi(l1.b, l2.b, l1.a);
 66      p.x = (l2.a.x * dot2 + l2.b.x * dot1) / (dot1 + dot2);
 67      p.y = (l2.a.y * dot2 + l2.b.y * dot1) / (dot1 + dot2);
 68 }
 69 
 70 bool judge(line l0, line l1, line l2){
 71      point p;
 72      get_point(l1, l2, p);
 73      return dblcmp(multi(p, l0.a , l0.b)) < 0;  
 74 }
 75 
 76 void SAI(){
 77      sort(ord, ord + ln , cmp); 
 78      int i, j;
 79      for (i = 0, j = 0; i < ln; ++i)
 80          if (dblcmp(l[ord[i]].angle - l[ord[j]].angle) > 0)
 81              ord[++j] = ord[i];
 82      ln = j + 1;
 83      q[0] = ord[0];
 84      q[1] = ord[1]; 
 85    /*  for (int i = 0; i < ln; ++i)
 86         printf("order[%d] = %d\n", i, ord[i]);*/
 87      
 88      bot = 0; 
 89      top = 1;
 90      for (int i = 2; i < ln ; ++i){
 91          while (bot < top && judge(l[ord[i]], l[q[top - 1]], l[q[top]])) --top;
 92          while (bot < top && judge(l[ord[i]], l[q[bot + 1]], l[q[bot]])) ++bot;
 93          q[++top] = ord[i];         
 94      }
 95      while (bot < top && judge(l[q[bot]], l[q[top-1]], l[q[top]])) --top; 
 96      while (bot < top && judge(l[q[top]], l[q[bot + 1]], l[q[bot]])) ++bot;
 97      q[++top] =  q[bot];
 98     // printf("top = %d bot = %d\n", top, bot);
 99    /*  for (int i = bot; i < top; ++i)
100         printf("q[%d] = %d\n", i, q[i]);*/
101      
102      for (n = 0, i = bot; i < top;  i++, n++)
103             get_point(l[q[i+1]], l[q[i]], p[n]);
104 }
105 
106 double getArea() {
107     if (n < 3) return 0;
108     double area = 0;
109     for (int i = 1; i < n-1; i++)
110         area += multi(p[0], p[i], p[i+1]);
111     return fabs(area)/2;
112 }
113 
114 int main(){
115     freopen("poj2451.in","r",stdin);
116     freopen("poj2451.out","w",stdout);
117     init();
118     SAI();
119     printf("%.1lf\n",getArea());
120     fclose(stdin); fclose(stdout);       
121 }