首页 > 代码库 > poj 2704

poj 2704

2024-07-14 18:16:54   222人阅读

题意：从一条线段(property)上观察另一与之平行的线段(house)，其中有很多与它们都平行的线段(障碍物)，求在property得可见整条线段house的最长连续范围的长度。

初时的想法是，求出在哪些点的范围可以看到整个HOUSE。 后来在DIS上找了几组数据，就变得都要特判了。再想想，既然找可行点不行，就找不可行的点，就是在哪些点的范围不能看到整个HOUSE。这样，代码就简化了。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;int n;const double eps=0.00000001;struct point{	double x,y;}st,en;struct line{	point start,end;}obst[200],house,pl;struct xcor{	double p;	int flag;	xcor(){ flag=0;}}xx[1200];int xxc; double tmp;void slove(point s, point t){	if(s.x==t.x){	tmp=t.x;	}	else{	double k=(s.y-t.y)/(s.x-t.x);	tmp=(pl.start.y-s.y)/k+s.x;	}	if(tmp>pl.end.x) tmp=pl.end.x;	if(tmp<pl.start.x) tmp=pl.start.x;}bool cmp(xcor A,xcor B){	if(A.p<B.p)return true;	else if(A.p==B.p){		if(A.flag<B.flag)return true;	}	return false;}int main(){	double a,b,c;	while(cin>>a>>b>>c){		if(a==0&&b==0&&c==0) break;		xxc=0;		st.x=a; st.y=c; en.x=b; en.y=c;		house.start=st; house.end=en;		cin>>a>>b>>c;		st.x=a; st.y=c; en.x=b; en.y=c;		pl.start=st; pl.end=en;		cin>>n; 		int co=0;		for(int i=0;i<n;i++){			cin>>a>>b>>c;			if(c<house.start.y&&c>pl.start.y){			st.x=a; st.y=c; en.x=b; en.y=c;			obst[co].start=st; obst[co].end=en;			co++;			}		}		n=co;		for(int i=0;i<n;i++){			slove(house.end,obst[i].start);			xx[xxc].p=tmp; xx[xxc].flag=-1;			xxc++;			slove(house.start,obst[i].end);			xx[xxc].p=tmp; xx[xxc].flag=1;			xxc++;		}		sort(xx,xx+xxc,cmp);		int now=0; double pre,lo,tt;		pre=pl.start.x; lo=0; 		for(int i=0;i<xxc;i++){			if(now==0){				tt=xx[i].p-pre;				if(tt>lo) lo=tt;			}			now+=xx[i].flag;			pre=xx[i].p;		}		tt=pl.end.x-pre;		if(tt>lo) lo=tt;		if(lo>0)		printf("%0.2lf\n",lo);		else printf("No View\n");	}}

　　


联系
我们