poj 1408

题意：在x轴，x = 1，y轴，y = 1.这四条线段上给出一些点，然后把x轴上的点和x = 1 上的点一一对应连接，把y轴上的点和y = 1上的点也一一对应连接，在这些连接线组成的四边形（除了定点外，不含其它的点）中，找出一个面积最大的

思路：求出所有的交点，然后求每一个四边形面积，找出最大输出即可，纠结了很久都不出结果，就是因为一个点保存的时候x写成了y，真杯具。

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <math.h>
  4 #include <stdlib.h>
  5 #include <iostream>
  6 #define N 2000
  7 
  8 using namespace std;
  9 
 10 struct node
 11 {
 12     double x;
 13     double y;
 14 };
 15 int n;
 16 node sx[N][2];
 17 node zy[N][2];
 18 node point[N][N];
 19 void init()
 20 {
 21     int i;
 22     point[0][0].x = point[0][0].y = point[n + 1][0].y = point[0][n + 1].x = 0;
 23     point[n + 1][0].x = point[0][n + 1].y = point[n + 1][n + 1].x = point[n + 1][n + 1].y = 1; // ******
 24     for(i = 1;i <= n; i++)
 25     {
 26         scanf("%lf",&sx[i][0].x);
 27         sx[i][0].y = 0;
 28     }
 29     for(i = 1;i <= n; i++)
 30     {
 31         scanf("%lf",&sx[i][1].x);
 32         sx[i][1].y = 1;
 33     }
 34     for(i = 1;i <= n; i++)
 35     {
 36         scanf("%lf",&zy[i][0].y);
 37         zy[i][0].x = 0;
 38     }
 39     for(i = 1;i <= n; i++)
 40     {
 41         scanf("%lf",&zy[i][1].y);
 42         zy[i][1].x = 1;
 43     }
 44     for(i = 1;i <= n; i++)
 45     {
 46         point[i][0] = sx[i][0];
 47         point[i][n + 1] = sx[i][1];
 48         point[0][i] = zy[i][0];
 49         point[n + 1][i] = zy[i][1];
 50     }
 51 }
 52 node jiaodian(node a1,node a2,node a3,node a4)  // 四种情况求交点
 53 {
 54     node p;
 55     double k1,k2,b1,b2;
 56     if(a1.x == a2.x)
 57     {
 58         if(a3.y == a4.y)
 59         {
 60             p.x = a1.x;p.y = a3.y;
 61         }
 62         else
 63         {
 64             k1 = a4.y - a3.y;
 65             p.x = a1.x;
 66             p.y = (k1 * p.x) + a3.y;
 67         }
 68     }
 69     else
 70     {
 71         k1 = 1 * 1.0 / (a2.x - a1.x);
 72         b1 = -1 * k1 * a1.x;
 73         if(a3.y == a4.y)
 74         {
 75             p.y = a3.y;
 76             p.x = (p.y - b1) / k1;
 77         }
 78         else
 79         {
 80             k2 = a4.y - a3.y;
 81             b2 = a3.y;
 82             p.x = (b2 - b1) * 1.0 / (k1 - k2);
 83             p.y = k2 * p.x + b2;
 84         }
 85     }
 86     //cout<<"P"<<p.x<<" "<<p.y<<endl<<endl;
 87     return p;
 88 }
 89 double qmianji(node a1,node a2,node a3,node a4) // 叉积求多边形面积
 90 {
 91     node temp[10];                        // 参考链接http://blog.csdn.net/hbzjklqh/article/details/6707819
 92     temp[0] = a1;
 93     temp[1] = a2;
 94     temp[2] = a3;
 95     temp[3] = a4;
 96     int i;
 97     double kemp = 0,cemp = 0;
 98     double s;
 99     for(i = 0;i < 4; i++)
100     {
101         kemp += temp[i].x * temp[(i + 1) % 4].y;
102         cemp += temp[i].y * temp[(i + 1) % 4].x;
103     }
104     //cout<<kemp<<" "<<cemp<<endl;
105     s = fabs(kemp - cemp) / 2;
106     //cout<<s<<endl;
107     return s;
108 }
109 int main()
110 {
111     int i,j;
112     double mianji[N];
113     freopen("data.txt","r",stdin);
114     while(cin>>n,n)
115     {
116         memset(mianji,0,sizeof(mianji));
117         init();
118         for(i = 1; i <= n; i++)
119         {
120             for(j = 1; j <= n; j++)
121             {
122                 point[i][j] = jiaodian(sx[i][0],sx[i][1],zy[j][0],zy[j][1]);
123             }
124         }
125         double maxx = 0;
126         int k = 0;
127         for(i = 0; i <= n; i++)
128         {
129             for(j = 0; j <= n; j++)
130             {
131                 mianji[k++] = qmianji(point[i][j],point[i + 1][j],point[i + 1][j + 1],point[i][j + 1]);
132             }
133         }
134         for(i = 0; i <= (n + 1) * (n + 1) ; i++)
135         {
136             if(maxx < mianji[i]) maxx = mianji[i];
137         }
138         printf("%.6lf\n",maxx);
139     }
140     return 0;
141 }