1066.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"
#include<vector>
#include <algorithm>
#define max(a,b) ((a)>=(b))?(a):(b)
using namespace std;
struct point
{double x,y;};
	

struct line
{point a,b;};
line l[32];


inline double cheng(point &a,point &b,point &c)
{return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);}

inline double jl(point a,point b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

int jiao(line l1,line l2)
{double s1=cheng(l1.a,l1.b,l2.a),
	s2=cheng(l1.a,l1.b,l2.b),s3,s4,lx,ly;
	if(s1*s2>0)return 0;
	if(s1*s2<0){if(cheng(l2.a,l2.b,l1.a)*cheng(l2.a,l2.b,l1.b)<=0)return 1;
			else return 0;}
	if(s1*s2==0){s3=cheng(l2.a,l2.b,l1.a);
		     s4=cheng(l2.a,l2.b,l1.b);
		     if(s3*s4<0)return 1;
		     if(s3*s4>0)return 0;
		     lx=jl(l1.a,l1.b);
		     ly=jl(l2.a,l2.b);
	             if(max(max(jl(l1.a,l2.a),jl(l1.b,l2.a)),max(jl(l1.a,l2.b),jl(l1.b,l2.b)))<=lx+ly)return 1;
		     else return 0;
	}
}
int cmp(double a,double b)
{return a>b;}

int main()
{int n,i,m,j,answer,t;double d[4][60];int num[4];
	vector<double> dv[4];
	line l_t;
	//cin>>t;
	//while(t--)
	{
	cin>>n;
	
	for(i=0;i<4;i++){d[i][0]=0;d[i][1]=100;num[i]=2;}
	
	for(i=0;i<n;i++)
	{cin>>l[i].a.x>>l[i].a.y>>l[i].b.x>>l[i].b.y;
	if(l[i].a.x==0)d[2][num[2]++]=l[i].a.y;
	if(l[i].a.x==100)d[3][num[3]++]=l[i].a.y;

	if(l[i].a.y==0)d[0][num[0]++]=l[i].a.x;
	if(l[i].a.y==100)d[1][num[1]++]=l[i].a.x;

	if(l[i].b.x==0)d[2][num[2]++]=l[i].b.y;
	if(l[i].b.x==100)d[3][num[3]++]=l[i].b.y;
	                                                                        
	if(l[i].b.y==0)d[0][num[0]++]=l[i].b.x;
	if(l[i].b.y==100)d[1][num[1]++]=l[i].b.x;
	}
	cin>>l_t.a.x>>l_t.a.y;
	
	for(i=0;i<4;i++)
	{dv[i].resize(num[i]);
	for(j=0;j<num[i];j++)dv[i][j]=d[i][j];
	sort(dv[i].begin(),dv[i].end(),cmp);
	}
	
	answer=29999;				
	for(i=1;i<num[0];i++)
	{l_t.b.x=(dv[0][i]+dv[0][i-1])/2;
	l_t.b.y=0;
	m=0;
	for(j=0;j<n;j++)if(jiao(l_t,l[j]))m++;
	if(m<answer)answer=m;//cout<<l_t.b.x<<' '<<l_t.b.y<<' '<<
	//	l[1].a.x<<' '<<l[1].a.y<<jiao(l[1],l_t)<<endl;     }
	}	
	
	
	for(i=1;i<num[1];i++)
        {l_t.b.x=(dv[1][i]+dv[1][i-1])/2;
        l_t.b.y=100;
        m=0;
        for(j=0;j<n;j++)if(jiao(l_t,l[j]))m++;
        if(m<answer)answer=m;//cout<<l_t.b.x<<' '<<l_t.b.y<<endl;     }
	
        }
	
	for(i=1;i<num[2];i++)
        {l_t.b.y=(dv[2][i]+dv[2][i-1])/2;
        l_t.b.x=0;
        m=0;
        for(j=0;j<n;j++)if(jiao(l_t,l[j]))m++;
        if(m<answer)answer=m;//cout<<l_t.b.x<<' '<<l_t.b.y<<endl;     }
	
        }
	
	for(i=1;i<num[3];i++)
        {l_t.b.y=(dv[3][i]+dv[3][i-1])/2;
        l_t.b.x=100;
        m=0;
        for(j=0;j<n;j++)if(jiao(l_t,l[j]))m++;
        if(m<answer)answer=m;//cout<<l_t.b.x<<' '<<l_t.b.y<<endl;     }

        }
	
	cout<<"Number of doors = "<<answer+1<<endl;
	//if(t!=0)cout<<endl;
	}
	return 0;
}