作者在 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;
}
#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;
}