题意是一个世界有许多个国家，，每个国家有N个建筑，包括一个发电站和N-1个用电建筑，所有建筑围成的凸包就是这个国家的面积。一枚导弹如果在一个国家之内爆炸则可以使这个国家停电。
step 1：求出每个国家的凸包（我用水平排序就是各种坑，改叉乘排序才过，主要是后面求面积的时候需要这个叉乘排序的信息）。
step 2：判断每枚导弹是否在这个国家的范围之内。
step 3：求出所有停电的国家的面积。
就是计算几何的综合模拟水题，坑点就是要小心（QAQ||写计算几何的题目都是要小心）。
传送门：?pid=1616
#include <stdio.h>#include <math.h>#include <string.h>#include <algorithm>#include <iostream>#define maxn 105#define eps 1e-8using namespace std;struct Node {double x,y;};struct King{Node b[maxn];double area;int mark;int lenk;};King a[maxn];int lt;double fx ,fy;bool cmpconvex1(Node a1,Node a2){if((a1.x-fx)*(a2.y-fy)==(a1.y-fy)*(a2.x-fx)){if(a1.y == a2.y)return a1.x < a2.x;elsereturn a1.y < a2.y;}return (a1.x-fx)*(a2.y-fy)>(a1.y-fy)*(a2.x-fx);}double dot(double x1,double y1,double x2,double y2){return x1 * y2 – x2 * y1;}double cross(Node a1,Node a2,Node a3){return (a2.x-a1.x)*(a3.y-a2.y)-(a3.x-a2.x)*(a2.y-a1.y);}int ConvexHull(Node * p,Node * ans,int t){for(int i=1;i<t;i++){if(p[i].y==p[0].y){if(p[i].x<p[0].x)swap(p[i],p[0]);}else if(p[i].y<p[0].y){swap(p[i],p[0]);}}fx = p[0].x;fy = p[0].y;sort(p,p+t,cmpconvex1);int k=0;for(int j=0;j<t;j++){while(k>=2&&cross(ans[k-2],ans[k-1],p[j])<0){k–;}ans[k++] = p[j];}return k;}double GetArea(Node * ans,int lenc){double Area = 0;for(int i=0;i<lenc;i++){Area += dot(ans[i].x,ans[i].y,ans[(i+1)%lenc].x,ans[(i+1)%lenc].y);}return Area;}int is_inside(double x1,double y1,King a1){double TempArea = 0;for(int i=0;i<a1.lenk;i++){TempArea += fabs(dot(a1.b[i].x-x1,a1.b[i].y-y1,a1.b[(i+1)%a1.lenk].x-x1,a1.b[(i+1)%a1.lenk].y-y1));}//printf("%lf %lf\n",TempArea,a1.area);if(fabs(TempArea-a1.area)<eps)return 1;elsereturn 0;}void input(){int n;lt = 0;memset(a,0,sizeof(a));while(scanf("%d",&n),n+1){Node temp[maxn];Node ans[maxn];for(int i=0;i<n;i++){scanf("%lf %lf",&temp[i].x,&temp[i].y);}int lenc = ConvexHull(temp,ans,n);for(int i=0;i<lenc;i++){a[lt].b[i].x = ans[i].x;a[lt].b[i].y = ans[i].y;}a[lt].area = GetArea(ans,lenc);a[lt].lenk = lenc;lt++;}double x1,y1;while(~scanf("%lf %lf",&x1,&y1)){for(int i=0;i<lt;i++){if(is_inside(x1,y1,a[i])){a[i].mark = 1;}}}double zans = 0;for(int i=0;i<lt;i++){if(a[i].mark)zans += a[i].area;}printf("%.2f\n",zans/2);}void File(){freopen("a.in","r",stdin);freopen("a.out","w",stdin);}int main(void){//File();input();return 0;}
生活若剥去理想、梦想、幻想，那生命便只是一堆空架子
