http://poj.org/problem?id=3348 (题目链接)
题意
给出平面上n个点,以这n个点中的一些围成的多边形面积 div 50的最大值。
Solution
凸包求面积。
很好做,构造完凸包后从栈底开始向上求叉乘之和,也就是将凸包分成许多小三角形求面积和。
代码
// poj3348
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
#define inf 2147483640
#define LL long long
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
using namespace std;
inline LL getint() {
LL x=0,f=1;char ch=getchar();
while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
} const int maxn=10010;
struct point {int x,y;}p[maxn];
int s[maxn],n,top; int cross(point p0,point a,point b) {
return (a.x-p0.x)*(b.y-p0.y)-(a.y-p0.y)*(b.x-p0.x);
}
double dis(point a,point b) {
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a,point b) {
int t=cross(p[1],a,b);
if (t>0) return 1;
else if (t==1 && dis(a,p[1])<dis(b,p[1])) return 1;
else return 0;
}
void Graham() {
if (n==1) s[top=1]=1;
else if (n==2) {s[top=1]=1;s[++top]=2;}
else {
s[top=1]=1;s[++top]=2;
for (int i=3;i<=n;i++) {
while (top>1 && cross(p[s[top-1]],p[s[top]],p[i])<=0) top--;
s[++top]=i;
}
}
}
double Size() {
point p0=p[s[1]];
double sum=0;
for (int i=3;i<=top;i++) sum+=cross(p0,p[s[i-1]],p[s[i]]);
return sum/2;
}
int main() {
while (scanf("%d",&n)!=EOF) {
int k=1;
for (int i=1;i<=n;i++) {
scanf("%d%d",&p[i].x,&p[i].y);
if (p[i].x<p[k].x || (p[i].x==p[k].x && p[i].y<p[k].y)) k=i;
}
point p0=p[k];
p[k]=p[1];p[1]=p0;
sort(p+2,p+1+n,cmp);
Graham();
printf("%d\n",(int)Size()/50);
}
return 0;
}