http://poj.org/problem?id=1066
题目大意：有n条线段 他们都在这个房间里 最后有一个点代表起始位置
现在想通过墙出去 他只能爆破每个房间的中点的门 问最少的门通过的
分析： 刚开始就想到暴力写 但是一想好麻烦 头都大了 最后还是暴力 我把边存错了 调试了好久 就过了
先找到每条线段（包括边界）与所有的线段之间的交点求出来 然后从左往右排下序 把中点存到一个结构体里（把边界的点特殊处理一下）
处理所有的中点 能直接相连的就置成1 否则就是INF 最后地杰斯特拉跑一边 把边缘的点比较一下就好
用G++ 交 c++的话 就把fabs改成abs就好 反正它本身就是整形
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<ctype.h> #include<math.h> #include<queue> #include<algorithm> #include<iostream> using namespace std; #define N 2000 const double ESP = 1e-8; #define INF 0x3f3f3f3f #define memset(a,b) memset(a,b,sizeof(a)) int n; struct Point { double x,y; int step; Point (double x=0,double y=0):x(x),y(y) {} Point operator - (const Point &temp)const { return Point(x-temp.x,y-temp.y); } int operator * (const Point &temp)const { double t=(x*temp.y-y*temp.x); if(t>ESP) return 1; if(fabs(t)<ESP) return 0; return -1; } }; struct node { Point A,B; node (Point A=0,Point B=0):A(A),B(B) {} }; Point p[N],d[N]; node a[N]; Point line(Point u1,Point u2,Point v1,Point v2)///求交点 { Point ret=u1; double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x)); ret.x+=(u2.x-u1.x)*t; ret.y+=(u2.y-u1.y)*t; return ret; } int cmp(const void *aa,const void *bb) { struct Point *cc,*dd; cc=(struct Point *)aa; dd=(struct Point *)bb; if(cc->x!=dd->x) return cc->x-dd->x; else return cc->y-dd->y; } int G[N][N]; void serch(int o) { for(int i=0;i<=o;i++) { for(int j=0;j<=o;j++) { if(i==j) continue; int flag=0; for(int k=1;k<n;k++) { int k1=fabs((d[i]-a[k].A)*(a[k].B-a[k].A)+(d[j]-a[k].A)*(a[k].B-a[k].A)); int k2=fabs((a[k].A-d[j])*(d[i]-d[j])+(a[k].B-d[j])*(d[i]-d[j])); if(k1==0 && k2==0) { flag=1; break; } } if(flag==0) G[i][j]=1; } } } int vis[N],dis[N]; void dji(int s,int o) { memset(vis,0); for(int i=0;i<=o;i++) dis[i]=G[s][i]; for(int i=0;i<=o;i++) { int Min=INF,dist; for(int j=0;j<=o;j++) { if(!vis[j] && Min>dis[j]) { Min=dis[j]; dist=j; } } vis[dist]=1; for(int j=0;j<=o;j++) { dis[j]=min(dis[j],dis[dist]+G[dist][j]); } } } int main() { double x1,x2,y1,y2; while(scanf("%d",&n)!=EOF) { double x,y; for(int i=1; i<=n; i++) { scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); a[i]=node(Point(x1,y1),Point(x2,y2)); } n=n+1; a[n++]=node(Point(0,0),Point(0,100)); a[n++]=node(Point(0,0),Point(100,0)); a[n++]=node(Point(0,100),Point(100,100)); a[n++]=node(Point(100,0),Point(100,100)); scanf("%lf %lf",&x,&y); int o=0;///中点的个数 int h[N];///在边缘的点 int aa=0;///边缘点的个数 for(int i=1; i<n; i++) { memset(p,0); int b=0; for(int j=1; j<n; j++) { if(i==j) continue; int k=fabs((a[i].B-a[j].A)*(a[j].B-a[j].A)+(a[i].A-a[j].A)*(a[j].B-a[j].A)); int kk=fabs((a[j].B-a[i].A)*(a[i].B-a[i].A)+(a[j].A-a[i].A)*(a[i].B-a[i].A)); if(k!=2 && kk!=2)///如果两个线段相交 求交点 { p[b++]=line(a[i].A,a[i].B,a[j].A,a[j].B); } } qsort(p,b,sizeof(p[0]),cmp);///交点从左向右排序 for(int j=1;j<b;j++)///每一条线段的中点 { d[o]=Point((p[j].x+p[j-1].x)/2.0,(p[j].y+p[j-1].y)/2.0); if(d[o].x==0 || d[o].x==100 || d[o].y==0 || d[o].y==100)///边界点 { h[aa++]=o; } o++; } } d[o]=Point(x,y);///起始点 for(int i=0;i<=o;i++) { for(int j=0;j<=o;j++) G[i][j]=INF; } serch(o);///判断这两个中点是否能直接相连 dji(o,o);///最短路 int Min=INF; for(int i=0;i<aa;i++) { Min=min(Min,dis[h[i]]); } printf("Number of doors = %d ",Min); } return 0; }