#include #include #include #include #define maxn 505 #define inf 0x3f3f3f3f using namespace std; struct Point { int x,y; Point(int _x=0,int _y=0) : x(_x),y(_y) { } Point operator - (const Point& P) const { return Point(x-P.x,y-P.y); } int operator * (const Point& P) const { return x*P.y-y*P.x; } bool operator == (const Point& P) const { return x==P.x&&y==P.y; } } Pn[maxn],Pm[maxn]; int n,m; int dis[maxn][maxn]; bool init() { if (scanf("%d",&n)!=1) return 0; for (int i=1;i<=n;++i) scanf("%d%d",&Pn[i].x,&Pn[i].y); scanf("%d",&m); for (int i=1;i<=m;++i) scanf("%d%d",&Pm[i].x,&Pm[i].y); return 1; } inline bool line(Point a,Point b,Point c) { return ((a.x<=b.x)&&(b.x<=c.x))||((a.x>=b.x)&&(b.x>=c.x)); } inline bool spj(Point p,Point q) { for (int i=1;i<=n;++i) if (!line(p,Pn[i],q)) return 0; return 1; } int judge(Point p,Point q) { int lcnt=0,rcnt=0; for (int i=1;i<=n;++i) { int cmp=(q-p)*(Pn[i]-p); if (cmp<0) ++lcnt; if (cmp>0) ++rcnt; // if (cmp==0&&!line(p,Pn[i],q)) return 0; if (lcnt&&rcnt) return 0; } if (!lcnt&&!rcnt) return spj(p,q); if (lcnt) return 1; if (rcnt) return 2; return 3; } void solve() { for (int i=1;i<=m;++i) { dis[i][i]=inf; for (int j=i+1;j<=m;++j) { dis[i][j]=dis[j][i]=inf; if (Pm[i]==Pm[j]) continue; int flag=judge(Pm[i],Pm[j]); if (flag&1) dis[i][j]=1; if (flag&2) dis[j][i]=1; } } /*for (int i=1;i<=m;++i) { for (int j=1;j<=m;++j) cout<