自动搬运

查看原文

来自洛谷，原作者为

	Seauy I remember your song, sung by centuries of wind.

搬运于2025-08-24 22:18:52，当前版本为作者最后更新于2022-09-22 21:19:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

题目大意

• $n$ 个点的多边形，求出所有与原点连线段跟多边形交点不超过 $2$ 的顶点。

• $n \leq 2\times 10^5$，坐标为不超过 $10^6$ 的自然数。

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;
}