[CEOI2012] Printed Circuit Board 的题解

· · 题解

题目链接

题目大意

Solution

考虑求出 O 与顶点 i 的连线段与多边形有交点的边中，交点模长最小的那个。

这个东西可以直接上极坐标李超线段树，但注意到每条边两端点的极角形成区间 [\theta_L,\theta _R]，我们按极角做扫描线，\theta_L 处插入线段 \theta_R 处再删除，发现对于同时存在的两条线段，他们的与过 O 且倾斜角为 \theta 的直线交点，到 O 的距离相对大小不变。

因此按极角离散化后用堆维护扫描线即可，复杂度 O(n \log n)。

Code

#include<bits/stdc++.h>
#define Lson (now<<1)
#define Rson (now<<1|1)
using namespace std;

typedef long long ll;
typedef long double ld;

const int MAXN=2e5;

inline int Read()
{
    int res;char c;
    while(1) {c=getchar();if('0'<=c && c<='9') {res=c-'0';break;}}
    while(1) {c=getchar();if('0'<=c && c<='9') res=res*10+c-'0';else break;}
    return res;
}

inline ld Mold(ld x,ld y) {return sqrt(x*x+y*y);}

struct Point
{
    ld x,y,rho,dis;
    int ID,loc;
    inline void Scan() {x=Read(),y=Read(),rho=y/x,dis=Mold(x,y);}
}ver[MAXN+5];
bool cmp(Point a,Point b)
{return a.loc==b.loc ? a.dis<b.dis : a.loc<b.loc;}

int n;ld K;//当前斜率
ld dsc[MAXN+5];int dnum;
vector<int> ope[MAXN+5];
int ans[MAXN+5],tot;

inline int Search(ld x)
{
    for(int L=1,R=dnum,mid;1;)
    {
        mid=(L+R)>>1;
        if(x==dsc[mid]) return mid;
        if(dsc[mid]<x) L=mid+1;
        else R=mid-1;
    }
    return 0;
}

struct Segment
{
    ld k,b,cls;
    inline ld dis()
    {
        ld x,y;
        if(k<0 && b<0) x=-k,y=K*x;
        else {if(k==K) return cls; x=b/(K-k),y=K*x;}
        return Mold(x,y);
    }
}seg[MAXN+5];

//------------- Heap -------------
int data[MAXN+5],Tail,inv[MAXN+5];
inline void Insert(int x)
{
    ld v=seg[x].dis();
    int now=++Tail; data[now]=x,inv[x]=now;
    for(;now>1;now>>=1)
        if(v<seg[data[now>>1]].dis())
        {
            swap(data[now],data[now>>1]);
            swap(inv[data[now]],inv[data[now>>1]]); 
        }
        else break;
}
inline void Delete(int x)
{
    int now=inv[x];
    data[now]=data[Tail];
    inv[data[Tail]]=now;
    data[Tail--]=0;
    while(Lson<=Tail)
        if(Rson<=Tail)
        {
            if(seg[data[Lson]].dis()<seg[data[Rson]].dis())
            {
                swap(data[now],data[Lson]);
                swap(inv[data[now]],inv[data[Lson]]);
                now=Lson;
            }
            else
            {
                swap(data[now],data[Rson]);
                swap(inv[data[now]],inv[data[Rson]]);
                now=Rson;
            }
        }
        else
        {
            swap(data[now],data[Lson]);
            swap(inv[data[now]],inv[data[Lson]]);
            now=Lson;
        }
}

inline bool Judge(int a,int b)
{
    if(!b) return 1;
    return ver[a].dis<seg[b].dis();
}

int main()
{
    //freopen("3.in","r",stdin);
    //freopen("mine.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        ver[i].Scan();
        dsc[++dnum]=ver[i].rho;
        ver[i].ID=i;
    }
    sort(dsc+1,dsc+dnum+1),dnum=unique(dsc+1,dsc+dnum+1)-dsc-1;
    for(int i=1;i<=n;i++) ver[i].loc=Search(ver[i].rho);
    ver[n+1]=ver[1];
    for(int i=1;i<=n;i++)
    {
        if(ver[i].x==ver[i+1].x) seg[i]=Segment{-ver[i].x,-1};
        else
        {
            seg[i].k=(ver[i].y-ver[i+1].y)/(ver[i].x-ver[i+1].x);
            seg[i].b=ver[i].y-seg[i].k*ver[i].x;
        }
        seg[i].cls=min(ver[i].dis,ver[i+1].dis);//获取每条线段 
        int L=ver[i].loc,R=ver[i+1].loc; if(L>R) swap(L,R);
        if(L==R) continue;
        ope[L+1].push_back(i);
        ope[R].push_back(-i);
    }
    sort(ver+1,ver+n+1,cmp);

    for(int i=1,j=1;i<=dnum && j<=n;i++)
    {
        K=dsc[i];
        for(int k=0;k<ope[i].size();k++)
            if(ope[i][k]>0) Insert(ope[i][k]);
            else Delete(-ope[i][k]);
        if(Judge(j,data[1])) ans[++tot]=ver[j].ID;
        while(ver[j].loc==i && j<=n) ++j;
    }
    sort(ans+1,ans+tot+1);
    printf("%d\n",tot);
    for(int i=1;i<=tot;i++) printf("%d ",ans[i]);
    return 0;
}