首页 > 代码库 > POJ 1912 A highway and the seven dwarfs (凸包)
POJ 1912 A highway and the seven dwarfs (凸包)
【题目链接】 http://poj.org/problem?id=1912
【题目大意】
给出一些点,表示一些屋子,这些屋子共同组成了村庄,现在要建一些高速公路
问是否经过了村庄。
【题解】
这些屋子的关键点一定在凸包上,所以我们只要求出凸包,判断是否和线相交即可
我们求出与高速公路相近和近似相反的向量,判断连线是否与这条公路相交即可。
【代码】
#include <cstdio>#include <algorithm>#include <cmath>#include <vector>using namespace std;double EPS=1e-10;const double PI=acos(-1.0);double add(double a,double b){ if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0; return a+b;}struct P{ double x,y; P(){} P(double x,double y):x(x),y(y){} P operator + (P p){return P(add(x,p.x),add(y,p.y));} P operator - (P p){return P(add(x,-p.x),add(y,-p.y));} P operator * (double d){return P(x*d,y*d);} double dot(P p){return add(x*p.x,y*p.y);} //点积 double det(P p){return add(x*p.y,-y*p.x);} //叉积};bool cmp_x(const P& p,const P& q){ if(p.x!=q.x)return p.x<q.x; return p.y<q.y; }vector<P> convex_hull(P* ps,int n){ sort(ps,ps+n,cmp_x); int k=0; vector<P> qs(n*2); for(int i=0;i<n;i++){ while((k>1)&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--; qs[k++]=ps[i]; } for(int i=n-2,t=k;i>=0;i--){ while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--; qs[k++]=ps[i]; }qs.resize(k-1); return qs;}double dist(P p,P q){return sqrt((p-q).dot(p-q));}double normalize(double r){ if(r<-PI/2.0+EPS)r+=PI*2; return r;}double atan2(const P& p){ return normalize(atan2(p.y, p.x));}bool double_cmp(double a,double b){ return a+EPS<b;}const int MAX_N=100010;int N,n;P ps[MAX_N];double as[MAX_N];void solve(){ for(int i=0;i<N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y); vector<P> chs; if(N>1){ chs=convex_hull(ps,N); n=chs.size(); chs.push_back(chs[0]); } for(int i=0;i<n;i++)as[i]=atan2(chs[i+1]-chs[i]); sort(as,as+n,double_cmp); P p1,p2; while(~scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y)){ if(N<2){puts("GOOD");continue;} int x=upper_bound(as,as+n,atan2(p2-p1),double_cmp)-as; int y=upper_bound(as,as+n,atan2(p1-p2),double_cmp)-as; puts((((p2-p1).det(chs[x]-p1)*(p2-p1).det(chs[y]-p1)>-EPS))?"GOOD":"BAD"); }}int main(){ while(~scanf("%d",&N))solve(); return 0;}
POJ 1912 A highway and the seven dwarfs (凸包)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。