> 第二个数据是
> 10
> -521 -296
> -575 -419
> -516 -864
> -114 -106
> 187 295
> -404 12
> 840 -852
> 948 -405
> 247 704
> 1 170
> 
> 28638
> 
> #include<cstdio>
> #include<algorithm>
> using namespace std;
> #define MAX 10000
> typedef struct
> {
>     int x,y;
> }POINT;
> POINT tree[MAX];
> int n,sel_num;
> int doudis(POINT end,POINT from)
> {
>     return (end.x-from.x)*(end.x-from.x)+(end.y-from.y)*(end.y-from.y);
> }
> int crossmul(POINT fir,POINT sec,POINT mid)
> {
>     return (fir.x-mid.x)*(sec.y-mid.y)-(fir.y-mid.y)*(sec.x-mid.x);
> }
> bool cmp(const POINT fir,const POINT sec)
> {
>     if(crossmul(fir,sec,tree[0])>0)
>         return true;
>     return crossmul(fir,sec,tree[0])==0&&doudis(fir,tree[0])<doudis(sec,tree[0]);
> }
> int mul(POINT fir,POINT sec,POINT thi)
> {
>     return (fir.x-sec.x)*(sec.y-thi.y)-(fir.y-sec.y)*(sec.x-thi.x);
> }
> void Graham()
> {
>     int i,j;
>     int pt=0;
>     for(i=1;i<n;i++)
>         if(tree[i].y<tree[pt].y||(tree[i].y==tree[pt].y&&tree[i].x<tree[pt].x))
>             pt=i;
>     swap(tree[0],tree[pt]);
>     sort(tree+1,tree+n,cmp);
>     sel_num=3;
>     for(i=3;i<n;i++)
>     {
>         while(mul(tree[i],tree[sel_num-1],tree[sel_num-2])>=0)
>             sel_num--;
>         tree[sel_num++]=tree[i];
>     }    
> }
> //int area2()
> //{
> //    int i,s;
> //    s=tree[0].y*(tree[sel_num-1].x-tree[1].x);
> //    for(i=1;i<sel_num;i++)
> //        s+=tree[i].y*(tree[i-1].x-tree[(i+1)%sel_num].x);
> //    return s>0?s:-s;
> //}
> //int area2()
> //{
> //    int i,s;
> //    s=tree[0].x*tree[sel_num-1].y-tree[0].y*tree[sel_num-1].x;
> //    for(i=1;i<sel_num;i++)
> //        s+=tree[i-1].x*tree[i].y-tree[i-1].y*tree[i].x;
> //    return s>0?s:-s;
> //}
> int area2()
> {
>     int i,s;
>     s=0;
>     tree[sel_num]=tree[0];
>     for(i=0;i<sel_num;i++)
>     {
>         s+=tree[i].x*tree[i+1].y-tree[i].y*tree[i+1].x;
>   //      printf("%d\n",s);
>     }
>     return s>0?s:-s;
> }
> int main()
> {
>     int i;
>     scanf("%d",&n);
>     for(i=0;i<n;i++)
>         scanf("%d%d",&tree[i].x,&tree[i].y);
>     Graham();
>  //   printf("%d\n",sel_num);
> //    for(i=0;i<sel_num;i++)
> //        printf("%d %d\n",tree[i].x,tree[i].y);
>     printf("%d\n",area2()/100);
> //    while(1);
>     return 0;
> }
>     
>     
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 网上的东西
> #include<iostream.h>
> #include<math.h>
>  
> #define MAX 1000
>  
> int main()
> {
>  int n,i;
>  double point[MAX][2],area;
>  while(cin>>n&&n>=3){
>     for(i=0;i<n;i++) cin>>point[i][0]>>point[i][1];  //沿着多边形的边逐个输入各顶点坐标;
>   
>     area=0;
>     for(i=0;i<n;i++){
>         int next=(i+1)>=n?0:(i+1);
>         area+=(point[next][0]-point[i][0])*(point[next][1]+point[i][1])/2;  //使用向量法求解!!!
>     }
>     area=fabs(area);  //注意!!!
>     cout<<"area="<<area/50<<endl;
>  }
>  return 0;
> }
> /********************************************** 
> 寻找凸包的graham 扫描法 
> PointSet为输入的点集； 
> ch为输出的凸包上的点集，按照逆时针方向排列; 
> n为PointSet中的点的数目 
> len为输出的凸包上的点的个数 
> **********************************************/ 
> #include<stdio.h> 
> #include<math.h> 
> const double INF=1E200; 
> const double EP=1E-10; 
> #define PI acos(-1) 
> /*基本几何数据结构*/ 
> 
> //点(x,y) 
> struct POINT 
> { 
>    double x; 
>    double y; 
> }; 
> 
> 
> // 返回两点之间欧氏距离 
> double distance(POINT p1, POINT p2) 
> { 
>    return sqrt( (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); 
> } 
> /****************************************************************************** 
> r=multiply(sp,ep,op),得到(sp-op)*(ep-op)的叉积 
> r>0:ep在矢量opsp的逆时针方向； 
> r=0：opspep三点共线； 
> r<0:ep在矢量opsp的顺时针方向 
> *******************************************************************************/ 
> //叉积就是2向量形成的平行四边形的面积 
> double multiply(POINT sp,POINT ep,POINT op) 
> { 
>       return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y)); 
> } 
> 
> int partition(POINT a[],int p,int r) 
> { 
>    int i=p,j=r+1,k; 
>    double ang,dis; 
>    POINT R,S; 
>    k=(p+r)/2;//防止快排退化 
>    R=a[p]; 
>    a[p]=a[k]; 
>    a[k]=R; 
>    R=a[p]; 
>    dis=distance(R,a[0]); 
>    while(1) 
>    { 
>       while(1) 
>       { 
>          ++i; 
>          if(i>r) 
>          { 
>             i=r; 
>             break; 
>          } 
>          ang=multiply(R,a[i],a[0]); 
>          if(ang>0) 
>             break; 
>          else if(ang==0) 
>          { 
>             if(distance(a[i],a[0])>dis) 
>                break; 
>          } 
>       } 
>       while(1) 
>       { 
>          --j; 
>          if(j<p) 
>          { 
>             j=p; 
>             break; 
>          } 
>          ang=multiply(R,a[j],a[0]); 
>          if(ang<0) 
>             break; 
>          else if(ang==0) 
>          { 
>             if(distance(a[j],a[0])<dis) 
>                break; 
>          } 
>       } 
>       if(i>=j)break; 
>       S=a[i]; 
>       a[i]=a[j]; 
>       a[j]=S; 
>    } 
> a[p]=a[j]; 
> a[j]=R; 
> return j; 
> } 
> 
> void anglesort(POINT a[],int p,int r) 
> { 
>    if(p<r) 
>    { 
>       int q=partition(a,p,r); 
>       anglesort(a,p,q-1); 
>       anglesort(a,q+1,r); 
>    } 
> } 
> 
> void Graham_scan(POINT PointSet[],POINT ch[],int n,int &len) 
> { 
>       int i,k=0,top=2; 
>       POINT tmp; 
>       // 选取PointSet中y坐标最小的点PointSet[k]，如果这样的点有多个，则取最左边的一个 
>       for(i=1;i<n;i++) 
>             if ( PointSet[i].y<PointSet[k].y || 
>             (PointSet[i].y==PointSet[k].y) && (PointSet[i].x<PointSet[k].x) ) 
>                k=i; 
>       tmp=PointSet[0]; 
>       PointSet[0]=PointSet[k]; 
>       PointSet[k]=tmp; // 现在PointSet中y坐标最小的点在PointSet[0] 
>       /* 对顶点按照相对PointSet[0]的极角从小到大进行排序，极角相同 
>                   的按照距离PointSet[0]从近到远进行排序 */ 
>       anglesort(PointSet,1,n-1); 
> 
>                ch[0]=PointSet[0]; 
>                ch[1]=PointSet[1]; 
>                ch[2]=PointSet[2]; 
>                for (i=3;i<n;i++) 
>                   { 
>                      while (multiply(PointSet[i],ch[top],ch[top-1])>=0) top--; 
>                      ch[++top]=PointSet[i]; 
>                   } 
>                len=top+1; 
> } 
> 
> #define M 100000 
> POINT a[M],b[M];
> int main() 
> { 
>     
>    int n,i,l; 
>    scanf("%d",&n); 
>    for(i=0;i<n;i++) 
>       scanf("%lf %lf",&a[i].x,&a[i].y); 
>    Graham_scan(a,b,n,l); 
>    for(i=0;i<l;i++)
>       printf("%lf %lf\n",b[i].x,b[i].y);
>    while(1);
>    return 0; 
> }
> 
> 
>     

• Re:Um... (153) seunghun93 2008-02-13 23:00:43