hdu 1616 计算几何 凸包
来源：程序员人生 发布时间：2015-08-05 07:53:52 阅读次数：3789次
题意是1个世界有许多个国家，每一个国家有N个建筑，包括1个发电站和N⑴个用电建筑，所有建筑围成的凸包就是这个国家的面积。1枚导弹如果在1个国家以内爆炸则可使这个国家停电。
step 1：求出每一个国家的凸包（我用水平排序就是各种坑，改叉乘排序才过，主要是后面求面积的时候需要这个叉乘排序的信息）。
step 2：判断每枚导弹是不是在这个国家的范围以内。
step 3：求出所有停电的国家的面积。
就是计算几何的综合摹拟水题，坑点就是要谨慎（QAQ||写计算几何的题目都是要谨慎）。
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1616
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#define maxn 105
#define eps 1e⑻
using 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;
else
return 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⑵],ans[k⑴],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
",TempArea,a1.area);
if(fabs(TempArea-a1.area)<eps)
return 1;
else
return 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
",zans/2);
}
void File(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdin);
}
int main(void){
//File();
input();
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
