pku3348cows

作者在 2010-08-01 18:03:55 发布以下内容
题目:pku3348
码:
//1 ≤ n ≤ 10000    where -1000 ≤ x, y ≤ 1000

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

/*==================================================*\
| Graham 求凸包 O(N * logN)
| CALL: nr = graham(pnt, int n, res); res[]为凸包点集;
\*==================================================
*/
struct point { long x, y; };
bool mult(point sp, point ep, point op)  //计算叉积
{
     return (sp.x - op.x) * (ep.y - op.y)
         >= (ep.x - op.x) * (sp.y - op.y);
}
bool operator < (const point &l, const point &r)
{
     return l.y < r.y || (l.y == r.y && l.x < r.x);
}
int graham(point pnt[], int n, point res[])
{
     int i, len, k = 0, top = 1;
     sort(pnt, pnt + n);      //需要包含algorithm头文件
     if (n == 0) return 0; res[0] = pnt[0];
     if (n == 1) return 1; res[1] = pnt[1];
     if (n == 2) return 2; res[2] = pnt[2];
     for (i = 2; i < n; i++)    //左链
     {
         while (top && mult(pnt[i], res[top], res[top-1]))
              top--;
         res[++top] = pnt[i];
     }
     len = top; res[++top] = pnt[n - 2];
     for (i = n - 3; i >= 0; i--)  //右链
     {
         while (top!=len && mult(pnt[i], res[top],res[top-1])) top--;
         res[++top] = pnt[i];
     }                    
     return top;   // 返回凸包中点的个数
}   //  graham(p,n,res)

//判断点p是否在以la,lb为端点的线段上
bool p_in_line(point p,point la,point lb)
{
     return (p.x-la.x)*(lb.y-la.y)==(p.y-la.y)*(lb.x-la.x);    
}
typedef point polygon[10005];

long polygon_area(polygon p,int n)
{  
    long area=0;  
    int i;
    for (i=1; i<=n ;i++)
       area+=p[i-1].x*p[i%n].y-p[i%n].x*p[i-1].y;
    return area;
}


int main()
{
    int n,m;
    int i,j;
    long area;
    polygon pp;
    point p[10005],res[10005];
    while(cin>>n)
    {
        for(i=0;i<n;i++)
            cin>>p[i].x>>p[i].y;
        m=graham(p,n,res);
        for(i=0;i<m;i++){ pp[i].x=res[i].x;pp[i].y=res[i].y; }
        area=polygon_area(pp,m);
        /*
        for(i=0;i<m-2;i++)
        {
            area+=(res[i].x*res[i+1].y+res[i+1].x*res[(i+2)%m].y+res[(i+2)%m].x*res[i].y
                           -res[i+1].x*res[i].y-res[i+2].x*res[i+1].y-res[i].x*res[(i+2)%m].y);
        }
        
*/
        if(area<0)area=-area;
        area/=2;
        cout<<area/50<<endl;
    }
    return 0;
}
 
计算几何 | 阅读 843 次
文章评论,共0条
游客请输入验证码
最新评论