开始正经的学计算几何，恩，是的没错～
加油～
题意：给定一个长方形，在里面加上不相交的线，然后给若干点，求这些点落在哪个区域。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#define N 500015
#define INF 1000000
#define ll long long
using namespace std;
struct Point
{
int x,y;
Point(){}
Point(int _x,int _y)
{
x = _x;y = _y;
}
Point operator -(const Point &b)const
{
return Point(x - b.x,y - b.y);
}
int operator *(const Point &b)const
{
return x*b.x + y*b.y;
}
int operator ^(const Point &b)const
{
return x*b.y - y*b.x;
}
};
struct Line
{
Point s,e;
Line(){}
Line(Point _s,Point _e)
{
s = _s;e = _e;
}
}; int xmult(Point p0,Point p1,Point p2) //计算p0p1 X p0p2
{
return (p1-p0)^(p2-p0);
}
const int MAXN = ;
Line line[MAXN];
int ans[MAXN];
int main(void)
{
int n,m,x1,y1,x2,y2,i;
int ui,li;
int cnt = ;
while(scanf("%d",&n),n)
{
if(cnt == ) cnt = ;
else printf("\n");
scanf("%d %d %d %d %d",&m,&x1,&y1,&x2,&y2);
for(i = ; i < n; i++)
{
scanf("%d%d",&ui,&li);
line[i] = Line(Point(ui,y1),Point(li,y2));
}
line[n] = Line(Point(x2,y1),Point(x2,y2)); int x,y;
Point p;
memset(ans,,sizeof(ans)); while(m--)
{
scanf("%d %d",&x,&y);
p = Point(x,y);
int l = ,r = n,tmp = ;
while(l <= r)
{
int mid = (l + r)/;
if(xmult(p,line[mid].s,line[mid].e) < )
{
tmp = mid;
r = mid - ;
}
else
l = mid + ;
}
ans[tmp]++;
}
for(i = ; i <= n; i++)
printf("%d: %d\n",i,ans[i]);
}
return ;
}