新建 文本文档.txt

2007年百度之星初试和复试的题目,大家可以做作,看看自己的水平

#include<iostream>
#include<cmath>
using namespace std;
const double zero=1e-6;
const int maxl=2000;
const int maxn=52;
const double limit=1e8;
struct point{
   double x,y;
};
point p[maxl],a[maxn],b[maxn],s,t,c;
int la,i,j,k,n,len,z[maxl],tot;
double d[maxl],ab,h,ac,v[maxl],g[maxl][maxl],ans,mi;
void add(point r){
   for(int i=1;i<=len;i++)
      if(fabs(p[i].x-r.x)+fabs(p[i].y-r.y)<zero)
         return;
   p[++len]=r;
}
double sqr(double r){
   return r*r;
}
double cha(point a,point b,point c){
   return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dis(point a,point b){
   return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
void check(point a,point b,point c,point d){
   double s1=cha(a,b,c),s2=cha(a,b,d);
   if(s1*s2<-zero&&cha(c,d,a)*cha(c,d,b)<-zero){
      point poi;
      poi.x=(s2*c.x-s1*d.x)/(s2-s1);
      poi.y=(s2*c.y-s1*d.y)/(s2-s1);
      add(poi);
   }
}
int main(){
   cin>>n;
   len=0;
   for(i=1;i<=n;i++)
      cin>>a[i].x>>a[i].y>>b[i].x>>b[i].y;
   cin>>s.x>>s.y>>t.x>>t.y;
   add(s);
   for(i=1;i<=n;i++){
      add(a[i]);
      add(b[i]);
   }
   for(i=1;i<=n;i++)
      for(j=i+1;j<=n;j++)
         check(a[i],b[i],a[j],b[j]);
   for(i=1;i<=n;i++){
      ab=dis(a[i],b[i]);
      h=fabs(cha(a[i],b[i],t)/ab);
      ac=sqrt(sqr(dis(a[i],t))-sqr(h));
      c.x=a[i].x+(b[i].x-a[i].x)/ab*ac;
      c.y=a[i].y+(b[i].y-a[i].y)/ab*ac;
      if(fabs(dis(c,t)-h)<zero&&fabs(dis(a[i],c)+dis(c,b[i])-ab)<zero)
         add(c);
   }
   for(i=1;i<=len;i++)
      for(j=1;j<=len;j++)
         g[i][j]=limit;
   for(i=1;i<=n;i++){
      tot=0;
      for(j=1;j<=len;j++)
         if(fabs(dis(a[i],p[j])+dis(p[j],b[i])-dis(a[i],b[i]))<zero){
            z[++tot]=j;
            v[tot]=dis(a[i],p[j]);
         }
      for(j=1;j<tot;j++)
         for(k=j+1;k<=tot;k++)
            if(v[j]>v[k]){
               swap(z[j],z[k]);
               swap(v[j],v[k]);
            }
      for(j=1;j<tot;j++){
         g[z[j]][z[j+1]]=v[j+1]-v[j];
         g[z[j+1]][z[j]]=v[j+1]-v[j];
      }
   }
   for(i=1;i<=len;i++)
      d[i]=limit;
   d[1]=0;
   la=1;
   for(i=1;i<=len;i++){
      for(j=1;j<=len;j++)
         if(d[la]+g[la][j]<d[j])
            d[j]=d[la]+g[la][j];
      d[la]=-d[la];
      for(j=1;j<=len;j++)
         if(d[la]<=0||d[j]>0&&d[j]<d[la])
            la=j;
   }
   for(i=1;i<=len;i++)
      d[i]=-d[i];
   mi=limit;
   for(i=1;i<=len;i++)
      if(dis(p[i],t)<mi&&d[i]<limit)
         mi=dis(p[i],t);
   ans=limit;
   for(i=1;i<=len;i++)
      if(fabs(dis(p[i],t)-mi)<zero&&ans>d[i])
         ans=d[i];
   printf("%.1f\n",ans);
   return 0;
}