【POJ-2318-TOYS】 判断点与直线的关系

POJ-2318-TOYS

题意
用n条总左到右排好序的直线分成将一个长方形分成n+1个区域，给你m个点，统计每个区域内点的个数
$1<=n,m<=5e3$
做法
$我们考虑$n^2$的做法即可，从左到右扫描每条线$
$判断当前点是否在这条线左侧，在左侧则计数并break$
代码

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define dbg(x) cout<<#x<<" = "<<x<<endlconst double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxn = 5005;
const int maxp = 1010;
int sgn(double x)
{
    if (fabs(x) <eps) return 0;if(x <0) return -1;return 1;
}
struct Point
{
    double x, y;Point() {
    }Point (double _x, double _y){
    x = _x, y = _y;}Point operator - (const Point &b) const{
    return Point(x - b.x, y - b.y);}double 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 relation(Point p)//判断点与直线的关系，1在左侧，2在右侧，3在直线上{
    int c = sgn( (p - s) ^ (e - s) );if (c < 0) return 1;else if (c > 0) return 2;return 3;}
};
Line l[maxn];
int sum[maxn];
int main()
{
    int n,m;int flag=0;double x,y,xa,ya,xb,yb,up,down;while(scanf("%d",&n)!=EOF){
    if(n==0)  break;else if(flag==0)  flag=1;else puts("");for(int i=0; i<=n; i++) sum[i]=0;scanf("%d%lf%lf%lf%lf",&m,&xa,&ya,&xb,&yb);for(int i=0;i<n;i++){
    scanf("%lf%lf",&up,&down);l[i]=Line(Point(up,ya),Point(down,yb));}l[n]=Line(Point(xb,ya),Point(xb,yb));for(int i=0;i<m;i++){
    scanf("%lf%lf",&x,&y);for(int j=0;j<=n;j++){
    if(l[j].relation(Point(x,y))==2){
    sum[j]++;break;}}}for(int i=0; i<=n; i++) printf("%d: %d\n",i,sum[i]);}return 0;
}