Description
Input
Output
Sample Input
12 3 3 4 6 4 11 4 8 10 6 5 7 6 6 6 3 7 9 10 4 10 9 1 7 5 20 20 20 40 40 20 40 40 30 30 3 10 10 21 10 21 13 -1 5 5 20 12
Sample Output
70.50
题意：给你N个王国，求下凸包，再求面积。给你一些炮弹，问炮弹炸掉的面积。（一个炮弹炸的话，整个王国都被炸了）。
思路：这题一看就是面积嘛，只不过需要判定点在哪个凸包里面才得取，而且每个凸包的面积只能取一次，因为炸掉的面积重新炸第二次就木有了。
不过与前几题练习不同的地方就是这里有很多个凸包，然后我一想，就把vector改成了二维的了……然后逗了……输入老是运行崩溃，妹妹滴！！！检查好久也看不出哪个错啊，而且已经把二维的长度给resize了还出错，改了一个多小时实在不行了，就看了眼奎神的代码……晕……就知道自己思想不够开放了。
干嘛跟vector过不去呢，把结构体开个数组不就解决了嘛！唉……自己还是太弱了，把结构体数组给忘了，哈哈……
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define eps 1e-8
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define f(i,a,n) for(i=a;i<n;i++)
#define F(i,a,n) for(i=a;i<=n;i++)
#define MM 100005
#define MN 505
#define INF 10000007
using namespace std;
typedef long long ll;
int sgn(const double &x){ return x < -eps? -1 : (x > eps);}
inline double sqr(const double &x){ return x * x;}
inline int gcd(int a, int b){ return !b? a: gcd(b, a % b);}
struct Point
{
double x, y;
Point(const double &x = 0, const double &y = 0):x(x), y(y){}
Point operator -(const Point &a)const{ return Point(x - a.x, y - a.y);}
Point operator +(const Point &a)const{ return Point(x + a.x, y + a.y);}
Point operator *(const double &a)const{ return Point(x * a, y * a);}
Point operator /(const double &a)const{ return Point(x / a, y / a);}
bool operator < (const Point &a)const{ return sgn(x - a.x) < 0 || (sgn(x - a.x) == 0 && sgn(y - a.y) < 0);}
bool operator == (const Point &a)const{ return sgn(sgn(x - a.x) == 0 && sgn(y - a.y) == 0);}
friend double det(const Point &a, const Point &b){ return a.x * b.y - a.y * b.x;}
friend double dot(const Point &a, const Point &b){ return a.x * b.x + a.y * b.y;}
friend double dist(const Point &a, const Point &b){ return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
void in(){ scanf("%lf %lf", &x, &y); }
void out()const{ printf("%lf %lf\n", x, y); }
};
struct Poly //多边形类
{
//vector<Point>a;
vector<Point>p; //顺时针凸包
vector<Point>tb;// 逆时针凸包
void in(const int &r)
{
p.resize(r); //不早凸包的时候可以把p改为a
for(int i = 0; i < r; i++) p[i].in();
}
//计算多边形的面积
double getArea()
{
int n = tb.size(); //平常的多边形就把tb换成a
double ans=0;
for(int i = 0; i < n; i++) ans += det(tb[i], tb[(i + 1)%n]);
return ans / 2;
}
//判断点集是否为凸包(返回m-1==n),或者用凸包点算出凸包顶点tb(本题即是)
void isCanHull()
{
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
int n = p.size();
tb.resize(n * 2 + 5);
int m = 0;
for(int i = 0; i < n; i++)
{
while(m > 1 && sgn(det(tb[m - 1] - tb[m - 2], p[i] - tb[m - 2])) <= 0)m--;
tb[m++] = p[i];
}
int k = m;
for(int i = n - 2; i >= 0; i--)
{
while(m > k && sgn(det(tb[m - 1] - tb[m -2], p[i] - tb[m - 2])) <= 0)m--;
tb[m++] = p[i];
}
tb.resize(m);
if(m > 1)tb.resize(m - 1);
//for(int i = 0; i < m - 1; i++) tb[i].out();
}
//判断点t(圆心)是否在凸包内部，这个是O(logn)的算法
int isContainOlogn(const Point &t)
{
int n = tb.size();
if(n < 3) return 0;
Point g = (tb[0] + tb[n / 3] + tb[n * 2 / 3] )/ 3.0;
int l = 0, r = n;
while(l + 1 < r)
{
int mid = (l + r) >> 1;
int k = sgn(det(tb[l] - g, tb[mid] - g) );
int dl = sgn(det(tb[l] - g, t - g) );
int dr = sgn(det(tb[mid] - g, t - g) );
if(k > 0)
{
if(dl >= 0 && dr < 0) r = mid;
else l = mid;
}
else
{
if(dl < 0 && dr >= 0) l = mid;
else r = mid;
}
}
r %= n;
int res = sgn(det(tb[l] - t, tb[r] - t));
if(res >= 0) return 1;
return 0;
}
}poly[MM];
double sum=0,a,b;
int n,i,k=0,vis[MM];
int main()
{
while(sca(n)&&n!=-1)
{
poly[k].in(n);
poly[k++].isCanHull();
}
while(~scanf("%lf%lf",&a,&b))
{
Point bb(a,b);
for(i=0;i<k;i++)
if(!vis[i]&&poly[i].isContainOlogn(bb)) sum+=poly[i].getArea(),vis[i]=1;
}
printf("%.2f\n",sum);
return 0;
}
POJ 1264 构建凸包判定点求面积,布布扣,bubuko.com
原文：http://blog.csdn.net/u011466175/article/details/21479289