【BZOJ1769】[Ceoi2009]tri

2016.03.19 10:38 Sat | 39次阅读 | 旧日oi | 固定链接 | 源码

题解

线段树+凸包

对于一个三角形,找到两个非原点对应的斜率区间,那么可能成为答案的点的斜率都在这个区间里,对于这些点,我们维护一个凸包,然后查询的时候只要在凸包上二分一下两个非原点形成的线段的斜率,就能找到离询问的三角形最近的点,判断一下就行了。
维护一段区间的凸包用线段树就行了。
复杂度nlog^2n。
我是rank倒第一,比倒第二慢3秒……

HINT

题面和数据去ceoi的官网搜就好了。

my code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
#define N 100005
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
struct Point
{
    double x,y;
    Point(double _,double __):x(_),y(__){}
    Point(){}
    Point operator +(const Point &a)const{
        return Point(x+a.x,y+a.y);
    }
    Point operator -(const Point &a)const{
        return Point(x-a.x,y-a.y);
    }
    double operator *(const Point &a)const{
        return x*a.y-y*a.x;
    }
    void read(){scanf("%lf%lf",&x,&y);}
    bool operator <(const Point &a)const{
        return atan2(y,x)<atan2(a.y,a.x);
    }
}p[N],st[N],t[N];
struct Line
{
    Point p,v;double alp;
    Line(Point a,Point b):p(a),v(b){
        alp=atan2(v.y,v.x);
    }
    Line(){}
};
struct Tri
{
    Point a,b;
}tri;
int n,m;
double slp[N];
vector<Point> v[N<<2];
vector<double> alp[N<<2];
bool cmp1(const Point &a,const Point &b)
{
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}
double dis(const Point &a)
{
    return a.x*a.x+a.y*a.y;
}
bool cmp2(const Point &a,const Point &b)
{
    double k=(a-t[1])*(b-t[1]);
    if(k==0) return dis(a-t[1])<dis(b-t[1]);
    return k>0;
}
void convex_hull(int l,int r,int rt)
{
    int n=r-l+1,top=0;
    if(n==1)
    {
        v[rt].push_back(p[l]);
        alp[rt].push_back(0);
        return;
    }
    for(int i=l;i<=r;i++) t[i-l+1]=p[i];
    sort(t+1,t+n+1,cmp1);
    sort(t+2,t+n+1,cmp2);
    st[1]=t[1];st[2]=t[2];top=2;
    for(int i=3;i<=n;i++)
    {
        while(top>=2&&(st[top]-st[top-1])*(t[i]-st[top-1])<=0) top--;
        st[++top]=t[i];
    }
    st[++top]=st[1];
    for(int i=top;i>1;i--) 
    {
        v[rt].push_back(st[i]);
        alp[rt].push_back(-atan2(st[i-1].y-st[i].y,st[i-1].x-st[i].x));
    }
}
void build(int l,int r,int rt)
{
    convex_hull(l,r,rt);
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lson);build(rson);
}
bool check(int rt,Line l)
{
    int x=lower_bound(alp[rt].begin(),alp[rt].end(),-l.alp)-alp[rt].begin();
    if(x==v[rt].size()) x=0;
    double tmp=Point(v[rt][x]-l.p)*l.v;
    return tmp<0;
}
bool find(int l,int r,int rt,int L,int R,Line line)
{
    if(L==l&&R==r) return check(rt,line);
    int mid=(l+r)>>1;
    if(R<=mid) return find(lson,L,R,line);
    else if(L>mid) return find(rson,L,R,line);
    else 
    {
        if(find(lson,L,mid,line)) return 1;
        if(find(rson,mid+1,R,line)) return 1;
        return 0;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i].read();
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++) slp[i]=atan2(p[i].y,p[i].x);
    build(1,n,1);
    for(int i=1;i<=m;i++) 
    {
        tri.a.read(),tri.b.read();
        double t1=atan2(tri.a.y,tri.a.x),t2=atan2(tri.b.y,tri.b.x);
        if(t1>t2) swap(t1,t2),swap(tri.a,tri.b);
        Line line=Line(tri.a,tri.b-tri.a);
        int l=lower_bound(slp+1,slp+n+1,t1)-slp;
        int r=upper_bound(slp+1,slp+n+1,t2)-slp-1;
        printf("%c\n",find(1,n,1,l,r,line)?'Y':'N');
    }
}