hdu 1616 計算幾何 凸包
來源：程序員人生 發布時間：2015-08-05 07:53:52 閱讀次數：3937次
題意是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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
