【刷题】BZOJ 5008 方师傅的房子

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

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

Sample Input

4
-2 -2
2 -2
2 2
-2 2
3
5 5
4 4
0 3

Sample Output

Solution

一个一个找显然是不行的

我们把第一个点作为基点，向其他所有点连边，这样就把凸多边形变成了若干个三角形（伪三角剖分。。）

因为给出的数据是已经排好序了的，所以对于每一个询问，我们先二分找到当前点属于哪一个三角形范围之内

之后就只要判断点是否在三角形之内就行了

还要注意一些小细节，比如凸多边形上1号点和n号点之间的范围，还有精度问题

最开始我写的是atan2的极角排序，后来怎么调也没过，现在还不知道是什么原因

后来对于每一凸包上的每一个点i，我们判断询问的点x是否在1点与i点连边的“左”方，一样可以达到效果

#include<bits/stdc++.h>

#define ll long long

const int MAXN=+,MAXM=+;

int n,m,x[MAXM],y[MAXM],ans,pre;

struct node{

    int x,y;

    double angle;

    inline bool operator < (const node &A) const {

        return angle<A.angle;

    };

    inline node operator - (const node &A) const {

        node tmp;

        tmp.x=x-A.x;

        tmp.y=y-A.y;

        return tmp;

    };

};

node point[MAXN];

template<typename T> inline void read(T &x)

{

    T data=,w=;

    char ch=;

    while(ch!='-'&&(ch<''||ch>''))ch=getchar();

    if(ch=='-')w=-,ch=getchar();

    while(ch>=''&&ch<='')data=((T)data<<)+((T)data<<)+(ch^''),ch=getchar();

    x=data*w;

}

template<typename T> inline void write(T x,char c='\0')

{

    if(x<)putchar('-'),x=-x;

    if(x>)write(x/);

    putchar(x%+'');

    if(c!='\0')putchar(c);

}

template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}

template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

inline ll cross(node a,node b)

{

    return (ll)a.x*(ll)b.y-(ll)b.x*(ll)a.y;

}

inline bool check(int dx,int dy)

{

    node q;

    q.x=dx;q.y=dy;

    if(cross(point[]-point[],q-point[])<)return false;

    if(cross(point[n]-point[],q-point[n])>)return false;

    int l=,r=n+;

    while(l<r)

    {

        int mid=(l+r)>>;

        if(cross(point[mid]-point[],q-point[mid])>)l=mid+;

        else r=mid;

    }

    if(cross(point[l]-point[l-],q-point[l])>=)return true;

    else return false;

}

int main()

{

    read(n);

    for(register int i=;i<=n;++i)read(point[i].x),read(point[i].y);

    read(m);

    for(register int i=;i<=m;++i)

    {

        read(x[i]);read(y[i]);

        if(i==);

        else if(pre)x[i]=x[i-]+x[i],y[i]=y[i-]+y[i];

        else x[i]=x[i-]-x[i],y[i]=y[i-]-y[i];

        if(check(x[i],y[i]))ans++,pre=;

        else pre=;

    }

    write(ans,'\n');

    return ;

}

5008 方师傅的房子