[POJ1912][凸包+二分]A highway and the seven dwarfs

POJ1912

分析：
先求凸包，然后问题转化为$O(logn)$O(logn)求直线是否与凸多边形相交
记录多边形每条边的斜率，然后二分求交点就行了

把一个double写成了int，wa了无数次

Code：

#include<bits/stdc++.h>
#define db double
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
const int N=1e5+5;
struct point{
	db x,y;
	point (){}
	point(db _x,db _y): x(_x),y(_y){}
	friend inline point operator - (const point &a,const point &b) {return point(a.x-b.x,a.y-b.y);}
	friend inline db operator * (const point &a,const point &b) {return a.x*b.y-a.y*b.x;}
	inline db dis() {return x*x+y*y;}
}p[N],st,ed;
inline bool cmp(const point &a,const point &b){
	db det=(a-p[1])*(b-p[1]);
	if(det) return det>0;
	return (a-p[1]).dis()<(b-p[1]).dis();
}
int n,top;
struct node{
	db ra;point a;
	inline friend bool operator < (const node &a,const node &b) {return a.ra<b.ra;}
}q[N];
inline void graham(){
	int t=1;
	for(int i=2;i<=n;i++) if(p[i].x<p[t].x || p[i].x==p[t].x && p[i].y<p[t].y) t=i;
	swap(p[t],p[1]);
	sort(p+2,p+n+1,cmp);
	for(int i=1;i<=n;i++){
		while(top>=2 && (p[top]-p[top-1])*(p[i]-p[top-1])<0) --top;
		p[++top]=p[i];
	}
	n=top,p[n+1]=p[1];
	for(int i=1;i<=n;i++) q[i].ra=atan2((p[i+1]-p[i]).y,(p[i+1]-p[i]).x),q[i].a=p[i];
	sort(q+1,q+n+1);
	q[n+1].ra=q[1].ra+2*acos(-1.0),q[n+1].a=q[1].a;
}
inline bool check(point a,point b){return ((st-a)*(ed-a))*((st-b)*(ed-b))<0;}
inline bool ok(){
	if(n<=1) return true;
	node t;	
	t.ra=atan2((ed-st).y,(ed-st).x);
	point a=q[lower_bound(q+1,q+n+1,t)-q].a;
	t.ra=atan2((st-ed).y,(st-ed).x);
	point b=q[lower_bound(q+1,q+n+1,t)-q].a;
	return !check(a,b);
}
int main(){
	n=read();
	for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
	if(n>1) graham();
	while(scanf("%lf%lf%lf%lf",&st.x,&st.y,&ed.x,&ed.y)!=EOF) ok()?puts("GOOD"):puts("BAD");
	return 0;
}