poj 3348 Cows 求凸包面积

题目链接

大意:

求凸包的面积。

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
const int maxn = ;
struct point
{
int x,y;
};
point a[maxn];
int st[maxn], top;
int cross(point p0,point p1,point p2)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
double dis(point p1,point p2)
{
return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
bool cmp(point p1,point p2)
{
int tmp=cross(a[],p1,p2);
if(tmp>) return true;
else if(tmp==&&dis(a[],p1)<dis(a[],p2)) return true;
else return false;
}
void init(int n)
{
int i,k;
point p0;
scanf("%d%d",&a[].x,&a[].y);
p0.x=a[].x;
p0.y=a[].y;
k=;
for(i=;i<n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
if( (p0.y>a[i].y) || ((p0.y==a[i].y)&&(p0.x>a[i].x)) )
{
p0.x=a[i].x;
p0.y=a[i].y;
k=i;
}
}
a[k]=a[];
a[]=p0; sort(a+,a+n,cmp);
}
void graham(int n)
{
int i;
if(n==) {top=;st[]=;}
if(n==)
{
top=;
st[]=;
st[]=;
}
if(n>)
{
for(i=;i<=;i++) st[i]=i;
top=; for(i=;i<n;i++)
{
while(top>&&cross(a[st[top-]],a[st[top]],a[i])<=) top--;
top++;
st[top]=i;
}
}
}
int main()
{
int n, r;
while(cin>>n) {
init(n);
graham(n);
double ans = ;
for(int i = ; i<top; i++) {
ans += (a[st[i]].x*a[st[i+]].y-a[st[i]].y*a[st[i+]].x);
}
ans += a[st[top]].x*a[st[]].y-a[st[top]].y*a[st[]].x;
ans /= ;
cout<<int(ans/)<<endl;
}
return ;
}
上一篇:【XSY2785】模型


下一篇:用python2.7,采集新浪博客