第二个数据是
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; 
}


    

• kick，谁说挂的……一交就ac了…… (6659) frkstyc 2007-08-24 02:29:01
  • Re:Um... (153) seunghun93 2008-02-13 23:00:43
• Re:第二个数据就挂了，找了一份凸包和一份求多边形面积，结果居然也挂了 (126) ecjtuGD 2008-08-27 15:24:50
  • Re:第二个数据就挂了，找了一份凸包和一份求多边形面积，结果居然也挂了 (186) notwhile 2009-07-15 09:45:13
    • Re:第二个数据就挂了，找了一份凸包和一份求多边形面积，结果居然也挂了 (11) 695375900 2009-08-14 21:18:54
      • Re:第二个数据就挂了，找了一份凸包和一份求多边形面积，结果居然也挂了 (13) msc_067 2010-06-16 08:41:13