[2022 national tournament simulation] polygon - computational geometry, binary answer, multiplication

Good questions without links

Title Description

Additional explanation ： Although the title refers to convex polygons , But it can not be closed . in other words , You can think of it as $m$ Intersection of two half planes . The distance from a point to an edge can be regarded as a line segment , It can also be seen as a straight line , It doesn't matter .

Answer key

We all know the reason why we fall into the category of art students

Why does it matter to regard it as the distance to a line segment or straight line , Because no matter what kind of distance , The distance from each edge to the origin should be equal , Otherwise, it must not be excellent . With this conclusion , We find that the perpendicular line from the origin to the straight line must intersect on the line segment .

First of all, understand that the answer is monotonous , Then you can split the answer . There is another monotonicity , namely $m$ The bigger the better .

Consider how to proceed $\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{c}\mathrm{k}$： First, for a feasible solution , We can rotate each straight line in one direction , Until it hits the point . It is easy to prove that each edge of any feasible solution can always be adjusted to intersect with the point , In this way, the only line to be considered is $n$ The article .

Consider a violent practice , We enumerate a straight line as the starting point , Then rotate the scan line , Clockwise each time （ Or counter clockwise ） Greedily find the first satisfaction No node appears in the middle of the two lines As the next line .（ Pictured above , Suppose the current line is $a$, that $b$ Is the next straight line to find ,$c$ and $d$ Are not ）
Until we find $m+1$ A straight line （ Including the starting point ）, Then judge whether the scanning line has swept a circle .

To do it directly is $O(n^2\log {ϵ}^{-1})$ Of , So let's preprocess the next line corresponding to each line , Then multiply .

The sum $O(n\log n\log {ϵ}^{-1})$.

Code

#include<bits/stdc++.h>//JZM yyds!!
#define ll long long
#define lll __int128
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define END putchar('\n')
#define lowbit(x) ((x)&-(x))
#define inline jzmyyds
using namespace std;
const int MAXN=1e5+5;
const ll INF=1e17;
ll read(){
    
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){
    if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='\n'){
    
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt>0)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
using pdd=pair<double,double>;
const double PI=acos(-1),eps=1e-7;
int n,m,sr[MAXN],k;
pdd tran(const pdd&a){
    
	pdd b;
	b.se=sqrt(a.fi*a.fi+a.se*a.se),b.fi=acos(a.fi/b.se);
	if(a.se<0)b.fi=PI*2-b.fi;
	return b;
}
double dis(const pdd&a,const pdd&b){
    
	pdd c(a.fi-b.fi,a.se-b.se);
	return sqrt(c.fi*c.fi+c.se*c.se);
}
pdd pa[MAXN],a[MAXN];
double b[MAXN],ch;
double F(double w){
    
	if(w<0)w+=PI*2;
	if(w>PI*2)w-=PI*2;
	return min(w,PI*2-w);
}
int jp[MAXN][25];
double jb[MAXN][25];
bool inl(double y,double r,int x){
    
	double ck=F(a[x].fi-y);
	return ck*2<PI&&a[x].se*cos(ck)>=r-eps;
}
bool check(const double&r){
    
	for(int i=1;i<=n;i++){
    
		b[i]=a[i].fi+acos(r/a[i].se);
		while(b[i]<0)b[i]+=PI*2;
		while(b[i]>=PI*2)b[i]-=PI*2;
		sr[i]=i;
	}
	sort(sr+1,sr+1+n,[](int x,int y){
    return b[x]<b[y];});
	for(int i=1,j=1;i<=n;i++){
    
		int x=sr[i];
		if(i==j)j=(j==n?1:j+1);
		while(j!=i&&inl(b[x],r,sr[j]))j=(j==n?1:j+1);
		jp[i][0]=j,jb[i][0]=b[sr[j]]-b[x];
		if(jb[i][0]<eps)jb[i][0]+=PI*2;
	}
	for(int j=1;j<=18;j++)for(int i=1;i<=n;i++)
		jp[i][j]=jp[jp[i][j-1]][j-1],jb[i][j]=jb[i][j-1]+jb[jp[i][j-1]][j-1];
	for(int i=1;i<=n;i++){
    
		int x=i;double s=0;
		for(int j=18;j>=0;j--)if((m>>j)&1)s+=jb[x][j],x=jp[x][j];
		if(s>PI*2-eps)return 1;
	}
	return 0;
}
const bool PF=0;
int main()
{
    
	freopen("polygon.in","r",stdin);
	freopen("polygon.out","w",stdout);
	n=read(),m=read(),k=1,ch=INF;
	for(int i=1;i<=n;i++){
    
		int x=read(),y=read();
		if(x==0&&y==0)return printf("%.9f\n",0.0),0;
		a[i]=tran(pa[i]=pdd(x,y)),ch=min(ch,a[i].se);
	}
	if(m>=n||PF)return printf("%.9f\n",ch),0;
	double l=0,r=ch,mid;
	for(int NND=30;NND--;){
    
		mid=(l+r)/2;
		if(check(mid))l=mid;
		else r=mid;
	}
	printf("%.9f\n",mid);
	return 0;
}