AcWing 2983. 玩具

AcWing 2983. 玩具

题目描述

代码

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;

namespace geometry{
    
    #define PI acos(-1)
    #define eps 1e-8
    struct PT {
    
        double x,y;
        PT() {
    x=0,y=0;}
        PT(double _x,double _y) {
    x=_x,y=_y;}
        friend ostream &operator<<(ostream &o,\
            const PT &X){
    
            o<<X.x<<' '<<X.y;
            return o;}
        friend istream &operator>>(istream &i,PT &X){
     
            i>>X.x>>X.y;
            return i;}
        PT operator-() {
    return PT(-x,-y);}
        PT& operator++() {
    x=x+1,y=y+1; return *this;}
        PT operator++(int) {
    
            PT T=*this; ++*this; return T;}
        PT& operator--() {
    x=x-1,y=y-1; return *this;}
        PT operator--(int) {
    
            PT T=*this; --*this; return T;}
        PT operator+(const PT &Y){
    
            PT T;
            T.x=this->x+Y.x;
            T.y=this->y+Y.y;
            return T;}
        PT operator-(const PT &Y){
    
            PT T;
            T.x=this->x-Y.x;
            T.y=this->y-Y.y;
            return T;}
        PT operator*(const double k){
    
            return PT(x*k,y*k);}
        PT operator*(const int k){
    
            return PT(x*k,y*k);}
        friend PT operator*(const double k, PT T){
    
            return T*k;}
        friend PT operator*(const int k, PT T){
    
            return T*k;}
        bool operator==(const PT &Y){
    
            return fabs(x-Y.x)<eps&&fabs(y-Y.y)<eps;}
        bool operator!=(const PT &Y){
    
        return !(fabs(x-Y.x)<eps&&fabs(y-Y.y)<eps);}
        double size(){
    return sqrt(x*x+y*y);}
        void rotate(double angle){
    
            double nx=x*cos(angle)+y*sin(angle);
            double ny=-x*sin(angle)+y*cos(angle);
            x=nx,y=ny;}
    };

    // struct LI { PT l,r;};
    int sign(double x){
    
        if (fabs(x) < eps) return 0;
        if (x < 0) return -1;
        return 1;
    }
    bool xless(const PT &X,const PT &Y){
    
        return X.x<Y.x;
    }
    bool xgreater(const PT &X,const PT &Y){
    
        return X.x>Y.x;
    }
    double dot(PT a, PT b) {
    return a.x*b.x+a.y*b.y;}
    double cross(PT a,PT b){
    return a.x*b.y-b.x*a.y;}
    double angle(PT a,PT b){
    
        return acos(dot(a,b)/a.size()/b.size());
    }
    double ang(double rad) {
    return rad/PI*180;}
    double rad(double ang) {
    return ang/180*PI;}
    PT line_x_line(PT p,PT v,PT q,PT w){
    
        PT u = p - q;
        double t = cross(w, u) / cross(v, w);
        return p + v * t;
    }
    double dist2line(PT p,PT l,PT r){
    
        PT v1 = r - l, v2 = p - l;
        return fabs(cross(v1, v2) / v1.size());
    }
    double dist2sgt(PT p,PT l,PT r){
    
        if (l == r) return (p-l).size();
        PT v1 = r - l, v2 = p - l, v3 = p - r;
        if(sign(dot(v1, v2))<0) return v2.size();
        if(sign(dot(v1, v3))>0) return v3.size();
        return dist2line(p,l,r);
    }
    PT line_proj(PT p,PT l,PT r){
    
        PT v = r - l;
        return l+v*(dot(v,p-l)/dot(v,v));
    }
    bool on_sgt(PT p,PT l,PT r){
    
        return sign(cross(p-l,p-r))==0&&\
            sign(dot(p-l,p-r))<=0;
    }
    bool sgt_x_sgt(PT l1,PT r1,PT l2,PT r2){
    
        double c1,c2,c3,c4;
        c1=cross(r1-l1,l2-l1),c2=cross(r1-l1,r2-l1);
        c3=cross(r2-l2,r1-l2),c4=cross(r2-l2,l1-l2);
        return sign(c1)*sign(c2)<=0&&\
            sign(c3)*sign(c4)<=0;
    }
    double area(double a,double b,double c){
    
        double p=(a+b+c)/2;
        return sqrt(p*(p-a)*(p-b)*(p-c));
    }
    double area(PT a,PT b,PT c){
    
        return fabs(cross((a-b),(b-c))/2);
    }
    double area(PT A,PT B){
    
        return cross(A,B)/2;
    }
    double polygon_area(PT p[], int n){
    
        double s = 0;
        for(int i = 1; i + 1 < n; i ++ )
            s+=cross(p[i]-p[0],p[i+1]-p[i]);
        return s / 2;
    }
}

using namespace geometry;
typedef long long LL;
const int N = 5010;

int n, m;
PT a[N], b[N];
int ans[N];

int find(PT X){
    
    int l = 0, r = n;
    while (l < r){
    
        int mid = l + r >> 1;
        if (area(b[mid]-a[mid], b[mid]-X) > 0) r = mid;
        else l = mid + 1;
    }
    return r;
}

int main(){
    
    bool is_first = true;
    while (scanf("%d", &n), n){
    
        LL x1, y1, x2, y2;//最左边的竖板用不到
        scanf("%d%lld%lld%lld%lld", &m, &x1, &y1, &x2, &y2);
        for (int i = 0; i < n; i ++ ){
    
            LL u, l;
            scanf("%lld%lld", &u, &l);
            a[i] = {
    u, y1}, b[i] = {
    l, y2};
        }
        a[n] = {
    x2, y1}, b[n] = {
    x2, y2};

        if (is_first) is_first = false;
        else puts("");
        memset(ans, 0, sizeof ans);
        while (m -- ){
    
            PT X; cin>>X;
            ans[find(X)] ++ ;
        }
        for (int i = 0; i <= n; i ++ )
            printf("%d: %d\n", i, ans[i]);
    }

    return 0;
}