poj 1408 Fishnet（计算几何）

题目：http://poj.org/problem?id=1408

题意：

一个1X1的正方形，每条边上有n个不同的点（不包括顶点），并给出它们的坐标。现在把对边相对应的点相连，将正方形分割成(n+1)*(n+1)个小四边形。问最大的四边形的面积是多少。

直接贴代码好了。。。

View Code

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 using namespace std;
  5 typedef struct node
  6 {
  7     double x,y;
  8 }point;
  9 point map[36][36];
 10 int n;
 11 double det(double x1,double y1,double x2,double y2)
 12 {
 13     return x1*y2-x2*y1;
 14 }
 15 double cross(point a,point b,point c,point d)
 16 {
 17     return det(b.x-a.x,b.y-a.y,d.x-c.x,d.y-c.y);
 18 }
 19 point jiaodian(point a,point b,point c,point d)
 20 {
 21     point h;
 22     double area1=cross(a,b,a,c);
 23     double area2=cross(a,b,a,d);
 24 
 25     h.x=(area2*c.x-area1*d.x)/(area2-area1);
 26     h.y=(area2*c.y-area1*d.y)/(area2-area1);
 27 
 28     return h;
 29 }
 30 double area(point a,point b,point c,point d)
 31 {
 32     double a2,a1;
 33     a1=fabs(0.5*cross(a,b,a,c));
 34     a2=fabs(0.5*cross(a,b,a,d));
 35     return a1+a2;
 36 }
 37 int main()
 38 {
 39     while(scanf("%d",&n)!=EOF)
 40     {
 41         if(n==0)
 42         break;
 43         int i,j;
 44         for(i=1;i<=n;i++)
 45         {
 46             scanf("%lf",&map[0][i].x);
 47             map[0][i].y=0;
 48         }//a
 49         for(i=1;i<=n;i++)
 50         {
 51             scanf("%lf",&map[n+1][i].x);
 52             map[n+1][i].y=1;
 53         }//b
 54         for(i=1;i<=n;i++)
 55         {
 56             scanf("%lf",&map[i][0].y);
 57             map[i][0].x=0;
 58         }//c
 59         for(i=1;i<=n;i++)
 60         {
 61             scanf("%lf",&map[i][n+1].y);
 62             map[i][n+1].x=1;
 63         }//d
 64         map[0][0].x=map[0][0].y=0;
 65         map[n+1][n+1].x=map[n+1][n+1].y=1;
 66         map[n+1][0].y=1;
 67         map[n+1][0].x=0;
 68         map[0][n+1].y=0;
 69         map[0][n+1].x=1;
 70         for(i=1;i<=n;i++)
 71         {
 72             point p;
 73             for(j=1;j<=n;j++)
 74             {
 75                 p=jiaodian(map[0][j],map[n+1][j],map[i][0],map[i][n+1]);
 76                 map[i][j]=p;
 77             }
 78 
 79         }
 80         /*for(i=0;i<=n+1;i++)
 81         {
 82             for(j=0;j<=n+1;j++)
 83             {
 84                 printf("(%f,%f) ",map[i][j].x,map[i][j].y);
 85             }
 86             printf("\n");
 87         }*/
 88         double res=0;
 89         for(i=0;i<=n;i++)
 90         {
 91             for(j=0;j<=n;j++)
 92             {
 93                 double uu;
 94                 uu=area(map[i][j],map[i+1][j+1],map[i+1][j],map[i][j+1]);
 95                 if(uu>res)
 96                 res=uu;
 97             }
 98         }
 99         printf("%.6f\n",res);
100     }
101     return 0;
102 }