[BZOJ4206]最大团（计算几何+dp）

2019-11-06 07:03:13

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

非二分图的最大团问题是npc hard（我不会告诉你我刚知道）所以今天gang了半天是毫无意义的（逃

一个非常奇妙的转化首先圆内和圆上的点扔掉对于每一个点做它的两条切线，每个点的两个切点在圆上会形成一段连续的弧，两个点不能同时选，当且仅当两个弧相离或包含栗子：这里写图片描述这两种情况都是不行的将圆展成一条链，跨越端点的线段就改为它的补集这样问题就变成了在一坨线段里选一些没有相离或包含关系的线段，并且数量最多将线段左端点排序，然后就变成了求关于右端点的最长上升子序列但是不能相离？强制一个线段选，做n次，这样求最长上升子序列的过程用二分优化一下时间复杂度O(n2logn) $O(n^2logn)$

第一次在bz上rk1，超鸡冻

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;const double pi=acos(-1.0);const double inf=1e18;int n,tmp,ans;double R,x,y,len,ang1,ang2,stack[2005];struct data{double x,y;bool flag;}s[2005];int cmp(data a,data b){ return a.flag<b.flag||(a.flag==b.flag&&a.x<b.x)||(a.flag==b.flag&&a.x==b.x&&a.y<b.y);}int find(double x){ int l=0,r=tmp,mid,ans=0; while (l<=r) { mid=(l+r)>>1; if (stack[mid]>=x) ans=mid,r=mid-1; else l=mid+1; } return ans;}int main(){ scanf("%d%lf",&n,&R); for (int i=1;i<=n;++i) { scanf("%lf%lf",&x,&y); len=sqrt(x*x+y*y); if (len<=R) { s[i].flag=1; continue; } ang1=atan2(y,x);ang2=acos(R/len); s[i].x=ang1-ang2;s[i].y=ang1+ang2; if (s[i].y>pi) s[i].y-=2*pi,swap(s[i].x,s[i].y); if (s[i].x<-pi) s[i].x+=2*pi,swap(s[i].x,s[i].y); } sort(s+1,s+n+1,cmp); for (int i=1;i<=n;++i) if (s[i].flag) {n=i-1;break;} stack[0]=-inf; for (int i=1;i<=n;++i) { if (s[i].flag) break; stack[tmp=1]=s[i].y; for (int j=i+1;j<=n;++j) if (s[j].x>s[i].y) break; else { if (s[j].y>stack[tmp]) { stack[++tmp]=s[j].y; continue; } int t=find(s[j].y); if (t!=1) stack[t]=s[j].y; } ans=max(ans,tmp); } PRintf("%d/n",ans);}

上一篇：C语言文件处理

下一篇：nrf24l01中文资料_工作原理_教程_程序

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注