题目大意:一根由平行线段组成的管道,给出管道的上端折点,下端折点比上端折点高度少1。有一束光从入口射入,求可以照到的最远位置。
思路:枚举任意两点,从入口处开始判断光线是否通过折点出(即与折点竖直线段相交)。记录最远位置并判断,输出即可。
开始脑抽,总觉的光要沿着入口上下点射入。。放了三天果断1A了。。
//Memory: 252K //Time: 63MS #include <iostream> #include <math.h> #include <string.h> #define EP 1E-7 #define INF 1E100 using namespace std; struct POINT { double x,y; };POINT p[50]; struct LINESEG { POINT s,e; };LINESEG l[50]; struct LINE //线a*x+b*y+c=0 { double a,b,c; POINT A; POINT B; LINE() {}; LINE( POINT _a, POINT _b) { A=_a; B=_b; a=B.y-A.y; b=A.x-B.x; c=B.x*A.y-A.x*B.y; }; }; double multiply(POINT sp,POINT ep,POINT op) { return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y)); } bool intersect_l(LINESEG u,LINESEG v) { return multiply(u.s,v.e,v.s)*multiply(v.e,u.e,v.s)>=0; } double lineintersect(LINESEG temp,LINE l2) // 是 L1,L2 返回交点p.x { LINE l1=LINE(temp.s,temp.e); double d=l1.a*l2.b-l2.a*l1.b; if(abs(d)<EP) // 不相交 return -INF; return (l2.c*l1.b-l1.c*l2.b)/d; } double solve(int n) { int i,j,k,mk=1; double maxx=-INF; LINESEG temp; for(i=1;i<n*2;i++) for(j=i+1;j<=n*2;j++) { temp.s=p[i]; temp.e=p[j]; for(k=1;k<=n;k++) { if(!intersect_l(l[k],temp)) break; } if((k-1)>=mk) { mk=k-1; if(mk==n) maxx=p[2*n].x; else { LINE l1=LINE(p[mk*2-1],p[mk*2+1]); LINE l2=LINE(p[mk*2],p[mk*2+2]); maxx=max(maxx,lineintersect(temp,l1)); maxx=max(maxx,lineintersect(temp,l2)); } } } return maxx; } int main() { int n,i,j; while(cin>>n && n) { j=1; for(i=1;i<=n;i++) { cin>>p[j].x>>p[j].y; p[j+1].x=p[j].x; p[j+1].y=p[j].y-1; l[i].s=p[j]; l[i].e=p[j+1]; j+=2; } double ans=solve(n); if(abs(ans-p[2*n].x)<EP) cout<<"Through all the pipe."<<endl; else printf("%.2lf\n",ans); } return 0; }