/*
题意:在一个矩形区域内,有n条线段,线段的端点是在矩形边上的
有一个特殊点treasure,问从这个点到矩形边的最少经过的线段(实际穿过线段时只能穿过中点)
枚举矩形外的每一段的中点与treasure连成一条线段link,判断这条线段经过的线段数目即可
因为围成的区域都是凸的,link闯过的线段必须要经过,不能绕过去
要理解穿过最少门的意思
参考http://hi.baidu.com/ackyclouday/blog/item/8c8665d299e94286a1ec9cfc.html
先按照极角排序,方便做很多!!
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 110;
const double EPS = 1e-8;
inline double fix_double(double x)
{
return fabs(x)<EPS ? 0.0 : x;
}
inline int sign(double x)
{
return x<-EPS?-1:x>EPS;
}
struct Point
{
double x,y;
Point(){}
Point(double _x , double _y)
{
x = _x;
y = _y;
}
bool operator == (const Point B)const
{
return sign(x-B.x)==0 && sign(y-B.y)==0;
}
Point operator - (const Point B)const
{
return Point(x-B.x , y-B.y);
}
};
//这里没考虑线段、直线 退化成点的情况
struct Segment
{
Point a,b;
Segment(){}
Segment(Point _a,Point _b)
{
a = _a;
b = _b;
}
};
//OA*OB = |OA|*|OB|*cos(AOB)
inline double dot(Point O , Point A , Point B)
{
Point OA = A - O;
Point OB = B - O;
return OA.x * OB.x + OA.y * OB.y;
}
//OA×OB = |OA|*|OB|*sin(AOB)
//>0 OB在OA的逆时针方向(右手螺旋)
//=0 OB跟OA共线
inline double cross(Point O , Point A , Point B)
{
Point OA = A - O;
Point OB = B - O;
return OA.x * OB.y - OB.x * OA.y;
}
//判断一个点是否在线段(包括端点)上 : 向量共线 , 点位于线段之间
//0 不在 1在线段内 2在端点处
int inSegment(Point pt , Segment seg)
{
if(sign(cross(pt,seg.a, seg.b)))return 0;
int ans = sign(dot(pt , seg.a , seg.b));
return ans == 0 ? 2 : ans < 0;
}
//线段和线段相交情况: 0:不相交, 1:规范相交, 2:交于端点 , 3:有重合部分
int across(Segment AB, Segment CD)//快速排斥实验 + 相互跨立(是相互)
{
if( max(AB.a.x , AB.b.x) < min(CD.a.x , CD.b.x) || max(AB.a.y , AB.b.y) < min(CD.a.y , CD.b.y)
|| max(CD.a.x , CD.b.x) < min(AB.a.x , AB.b.x) || max(CD.a.y , CD.b.y) < min(AB.a.y , AB.b.y) )
return 0;
int AB_CD = sign(cross(AB.a , AB.b , CD.a)) * sign(cross(AB.a , AB.b , CD.b));
int CD_AB = sign(cross(CD.a , CD.b , AB.a)) * sign(cross(CD.a , CD.b , AB.b));
//有重合部分
if(AB_CD == 0 && CD_AB == 0 && (inSegment(AB.a , CD) == 1 || inSegment(AB.b , CD) == 1 ) )return 3;
if(AB_CD < 0)//CD跨立AB
{
return CD_AB ==0 ? 2: CD_AB < 0;
}
else if(AB_CD == 0)return CD_AB <= 0 ? 2 : 0;
return 0;
}
int n;
Segment seg[MAXN];
Point treasure , pt[MAXN*10];
inline double dist(Point A , Point B)
{
double x = A.x - B.x;
double y = A.y - B.y;
return sqrt(x*x+y*y);
}
bool cmp(const Point &A , const Point &B)
{
Point zero = Point(0,0);
int ans = sign(cross(zero,A,B));
if(ans == 0 )return dist(zero,A) + EPS < dist(zero,B);
return ans > 0;
}
int solve()
{
int ans = n+1 , cnt = 0;
for(int i = 0; i < n; i++)
{
pt[cnt++] = seg[i].a;
pt[cnt++] = seg[i].b;
}
pt[cnt++] = Point(0,0);
pt[cnt++] = Point(100,100);
pt[cnt++] = Point(100,0);
pt[cnt++] = Point(0,100);
sort(pt,pt+cnt,cmp);//先按照极角排序,方便做很多!!
for(int i = 1; i < cnt; i++)
{
Point center = Point((pt[i].x+pt[i-1].x)/2 , (pt[i].y+pt[i-1].y)/2);
Segment link = Segment(treasure , center);
int tot = 0;
for(int j = 0; j<n ;j++)
{
if(across(link,seg[j]))tot++;
}
if(tot<ans)ans = tot;
}
return ans + 1;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("in","r",stdin);
#endif
double x1,y1,x2,y2;
while( ~scanf("%d",&n) )
{
for(int i = 0; i<n; i++)
{
scanf("%lf%lf%lf%lf",&seg[i].a.x,&seg[i].a.y,&seg[i].b.x,&seg[i].b.y);
}
scanf("%lf%lf",&treasure.x,&treasure.y);
printf("Number of doors = %d\n",solve());
}
return 0;
}