题目大意：给一个由墙围成的正方形，里面有若干墙，每次破墙只能从（当前看到的）墙的中点破，求最少破多少墙才能看到宝藏。
——————————————————————
显然枚举起点然后画一条以终点为端点的线，求线和多少墙相交即可。
但是我不会证明：这里有证明：
然后有该证明我们得到只要起点为这些线的端点即可。
#include#include #include #include #include #include #include using namespace std;typedef double dl;const int INF=2147483647;const int N=31;struct point{ //既是向量又是点 dl x; dl y;}p[2*N],ed;int n;inline point getmag(point a,point b){ point s; s.x=b.x-a.x;s.y=b.y-a.y; return s;}inline dl multiX(point a,point b){ return a.x*b.y-b.x*a.y;}inline int intersect(point a,point b){ int ans=0; if(a.x==b.x&&a.y==b.y)return 0; for(int i=1;i<=n;i++){ dl d1=multiX(getmag(a,p[i]),getmag(a,b))*multiX(getmag(a,p[i+n]),getmag(a,b)); dl d2=multiX(getmag(p[i],a),getmag(p[i],p[i+n]))*multiX(getmag(p[i],b),getmag(p[i],p[i+n])); if(d1<=0&&d2<=0)ans++; } return ans;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i+n].x,&p[i+n].y); } scanf("%lf%lf",&ed.x,&ed.y); if(n==0){ printf("Number of doors = 1\n"); return 0; } int ans=INF; for(int i=1;i<=2*n;i++){ ans=min(ans,intersect(p[i],ed)); } printf("Number of doors = %d\n",ans); return 0;}