bzoj5008: 方师傅的房子

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Description

方师傅来到了一个二维平面。他站在原点上，觉得这里风景不错，就建了一个房子。这个房子是n个点的凸多边形

，原点一定严格在凸多边形内部。有m个人也到了这个二维平面。现在你得到了m个人的坐标，你要判断这m个人中

有多少人在房子内部。点在凸多边形边上或者内部都认为在房子里面。

Input

第一行一个数n，接下来n行，每行两个整数x，y。输入按照逆时针顺序输入一个凸包。

接下来一个数m，最后有m行，第一行两个整数 x，y，表示第一个人的坐标。

对于第i个询问(i>=2) ，输入两个数dx，dy。

如果上一个人在房子内部，x[i]=x[i-1]+dx,y[i]=y[i-1]+dy。否则x[i]=x[i-1]-dx,y[i]=y[i-1]-dy。

n <= 100000， m <= 200000，输入保证所有人的坐标，房屋的坐标都在[-1e9，1e9]之内。

Output

输出一个数，在房子内部人的个数。

对每个询问，二分出凸包上对应位置进行判断，二分时可以用极角，当极角相近时换用叉积以减小误差。

#include<bits/stdc++.h>

typedef long long i64;

char buf[],*ptr=buf;

int _(){

    int x=,f=;

    while(*ptr<)*ptr++=='-'?f=-:;

    while(*ptr>)x=x*+*ptr++-;

    return x*f;

}

int n,m,ans=;

double a0;

const double _2pi=std::acos(-)*;

struct pos{

    int x,y;

    double a;

    void ga(){

        a=std::atan2(y,x)-a0;

        while(a<)a+=_2pi;

        while(a>=_2pi)a-=_2pi;

    }

    bool operator<(const pos&w)const{

        if(fabs(a-w.a)>1e-)return a<w.a;

        return *this*w>;

    }

    i64 operator*(const pos&w)const{return i64(x)*w.y-i64(y)*w.x;}

    pos operator-(const pos&w)const{return (pos){x-w.x,y-w.y};}

}ps[];

int query(pos p){

    p.ga();

    pos*p1=std::upper_bound(ps+,ps+n+,p);

    if((p1[-]-p)*(p1[]-p)>=)return ++ans,;

    return -;

}

int main(){

    fread(buf,,sizeof(buf),stdin);

    n=_();

    for(int i=;i<=n;++i)ps[i].x=_(),ps[i].y=_();

    a0=std::atan2(ps[].y,ps[].x);

    ps[].a=;

    for(int i=;i<=n;++i)ps[i].ga();

    ps[n+]=ps[];

    m=_();

    int x0=_(),y0=_();

    for(int i=,la=query((pos){x0,y0});i<=m;++i){

        x0+=_()*la,y0+=_()*la;

        la=query((pos){x0,y0});

    }

    printf("%d\n",ans);

    return ;

}