当前位置:网站首页>【2022国赛模拟】多边形——计算几何、二分答案、倍增
【2022国赛模拟】多边形——计算几何、二分答案、倍增
2022-07-06 19:11:00 【偶耶XJX】
好题无链接
题目描述
补充说明:题目虽然说的是凸多边形,但是它其实可以不封闭。也就是说,你可以看成是 m m m 个半平面的交。点到边的距离可以看成到线段,也可以看成到直线,其实无所谓。
题解
大家都知道落榜美术生的梗吧
为什么说看成到线段或直线的距离无所谓呢,是因为不管哪一种距离,每条边到原点的距离最好都相等,否则一定不优。有了这个结论,我们发现原点到直线的垂线一定交于线段上。
首先明白答案具有单调性,然后就可以二分答案了。另外还有一个单调性,即 m m m 越大越优。
考虑怎么进行 c h e c k \rm check check:首先对于一个可行的解,我们可以把每一条直线往一个方向旋转,直到撞到点上。容易证明任何可行解的每条边总可以调整到与点相交,这样一来需要考虑的直线就只有 n n n 条了。
考虑一个暴力做法,我们枚举一条直线作为起点,然后旋转扫描线,每次顺时针(或逆时针)贪心地找到第一条满足没有节点出现在两直线中间范围内的直线作为下一条。(如上图,假设当前直线为 a a a,那么 b b b 是要找的下一条直线, c c c 和 d d d 都不是)
直到总共找到 m + 1 m+1 m+1 条直线(包括起点),然后判断扫描线有没有扫过一圈即可。
直接做是 O ( n 2 log ϵ − 1 ) O(n^2\log \epsilon^{-1}) O(n2logϵ−1) 的,所以我们双指针预处理一下每条直线对应的下一条直线,然后倍增即可。
总复杂度 O ( n log n log ϵ − 1 ) O(n\log n\log \epsilon^{-1}) O(nlognlogϵ−1)。
代码
#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;
}
边栏推荐
- 1 -- Xintang nuc980 nuc980 porting uboot, starting from external mx25l
- MySQL --- 常用函数 - 字符串函数
- MySQL
- The third season of ape table school is about to launch, opening a new vision for developers under the wave of going to sea
- QPushButton-》函数精解
- The cities research center of New York University recruits master of science and postdoctoral students
- [Mori city] random talk on GIS data (II)
- 你不可不知道的Selenium 8种元素定位方法,简单且实用
- A new path for enterprise mid Platform Construction -- low code platform
- fiddler的使用
猜你喜欢
Web3's need for law
Have fun | latest progress of "spacecraft program" activities
Niuke programming problem -- double pointer of 101 must be brushed
C#/VB.NET 删除Word文档中的水印
How to build a 32core raspberry pie cluster from 0 to 1
Hash table and full comments
Electrical engineering and automation
Compress JS code with terser
Pioneer of Web3: virtual human
postgresql之整体查询大致过程
随机推荐
The so-called consumer Internet only matches and connects industry information, and does not change the industry itself
运维管理系统有哪些特色
Digital scrolling increases effect
Statistics of radar data in nuscenes data set
Go swagger use
Untiy文本框的代码换行问题
B站6月榜单丨飞瓜数据UP主成长排行榜(哔哩哔哩平台)发布!
安德鲁斯—-多媒体编程
阿里云易立:云原生如何破解企业降本提效难题?
安全交付工程师
Work of safety inspection
数字滚动增加效果
This week's hot open source project!
Apifox, is your API interface document rolled up like this?
写作系列之contribution
AWS学习笔记(一)
Difference and the difference between array and array structure and linked list
unity webgl自适应网页尺寸
Django数据库(SQlite)基本入门使用教程
牛客编程题--必刷101之双指针篇