3525.txt

半平面求交。zzy大牛论文改写的。有一定的实现。但有些功能没有尝试过

#include<cstdio>    
#include<cmath>  
#include<algorithm>  
using namespace std;
typedef	double ldb;
const	ldb leps = 1e-10 , le = 1e-8;
const	int maxn = 108; 

struct	node{ ldb  x,y; } d[maxn];
struct	line{ node a,b; } e[maxn]; 
ldb		ang[maxn]; 
int		o[maxn],D[maxn],n,m,sd,tot; 

inline	int sig(ldb x){ return x < -leps ? -1 : x > leps; }
inline	ldb det(node a,node b,node c){ return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); }  
void	cnode(node a,node b,node c,node d,node& ret){
		ldb s1 = det(c,b,a) , s2 = det(b,d,a);
		ret.x = (c.x*s2 + d.x*s1)/(s2 + s1);
		ret.y = (c.y*s2 + d.y*s1)/(s2 + s1);
}
inline	bool cmp(int u,int v){  
		if (sig(ang[u]-ang[v])==0) return sig(det(e[v].a,e[v].b,e[u].b)) >= 0; 
		return ang[u] < ang[v]; 
}  
bool	incde(int x,int y,int z) {  
		node tmp; 
		cnode(e[x].a,e[x].b,e[y].a,e[y].b,tmp); 
		return sig(det(e[z].a,e[z].b,tmp)) < 0; 
}  
bool	work(){  
		int i,f=1,r=f+1; 
		for(i=0; i<n; o[i]=i++) ang[i] = atan2(e[i].b.y-e[i].a.y,e[i].b.x-e[i].a.x);
		sort(o,o+n,cmp);
		for(i=1,m=1; i<n; i++) if (sig(ang[o[i-1]]-ang[o[i]])!=0) o[m++] = o[i]; 
		D[f] = o[0]; D[r] = o[1]; 
		for(i=2; i<m; i++){  
			while(f<r && incde(D[r-1],D[r],o[i])) r--; 
			while(f<r && incde(D[f+1],D[f],o[i])) f++; 
			D[++r] = o[i]; 
		}  
		while(f<r && incde(D[r-1],D[r],D[f])) r--; 
		while(f<r && incde(D[f+1],D[f],D[r])) f++; 
		//printf("%d", r-f);
		return (r-f>=2);
}  

line	s[maxn];

bool	can(ldb m){
		int i;
		ldb	dx,dy,t;
		for(i=0; i<n; i++){
			dx = s[i].b.x - s[i].a.x;
			dy = s[i].b.y - s[i].a.y;
			t = sqrt(m*m/(dx*dx+dy*dy));
			e[i].a.x = s[i].a.x-dy*t;
			e[i].a.y = s[i].a.y+dx*t;
			e[i].b.x = s[i].b.x-dy*t;
			e[i].b.y = s[i].b.y+dx*t;
		}
	//	printf("(%.0lf)",m);
	//	if (tot==2) 
	//		for(i=0; i<n; i++) printf("(%lf,%lf)-(%lf,%lf)\n",e[i].a.x,e[i].a.y,e[i].b.x,e[i].b.y);
		return work();
}

int		main(){
		int i;
		ldb sx,sy,tx,ty,ans,l,r,m;
//		freopen("input.txt","r",stdin);
		while(scanf("%d\n",&n)==1){
			if (n==0) break;
			scanf("%lf%lf",&sx,&sy);
			for(i=0; i<n-1; i++){
				scanf("%lf%lf",&tx,&ty);
				s[i].a.x = sx; s[i].a.y = sy;
				s[i].b.x = tx; s[i].b.y = ty;
				sx = tx; sy = ty;
			}
			s[n-1].a.x = sx; s[n-1].a.y = sy;
			s[n-1].b.x = s[0].a.x; s[n-1].b.y = s[0].a.y;
			ans = 0;
			l = 0; r = 100000;  tot = 0;
/*			for (int t = 300; t <= 1000; t++)
				can(t);*/
			while(r-l>le){
				m = (l+r)/2; ++tot;
				if (can(m)){
					ans = m;
					l = m;
				} r = m;
			}
			printf("%.6lf\n",ans);*/
			while (fabs(l-r) > le) {
				m = (l + r) / 2.0;
				if (can(m))
					l = m;
				else
					r = m;
			}
			printf("%.6lf\n", l + le);
		}
		return 0;