首页 > 代码库 > Codeforces 333E Summer Earnings ——Bitset
Codeforces 333E Summer Earnings ——Bitset
【题目分析】
找一个边长最大的三元环。
把边排序,然后依次加入。加入(i,j)时,把i和j取一个交集,看看是否存在,存在就找到了最大的三元环。
输出即可,n^3/64水过。
【代码】
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <set> #include <bitset> #include <map> #include <string> #include <algorithm> #include <vector> #include <iostream> #include <queue> using namespace std; #define maxn 3010 #define mlog 16 #define F(i,j,k) for (int i=j;i<=k;++i) #define inf (0x3f3f3f3f) int Getint() { int x=0,f=1; char ch=getchar(); while (ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} while (ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f; } struct edge{int l,r;double d;}e[maxn*maxn]; struct Point{int x,y;}a[maxn]; int n,cnt=0; bool cmp(edge x,edge y){return x.d>y.d;} bitset <maxn> b[maxn]; int main() { n=Getint(); F(i,1,n) { a[i].x=Getint(); a[i].y=Getint(); } F(i,1,n-1) F(j,i+1,n) { e[++cnt].l=i; e[cnt].r=j; e[cnt].d=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)); } sort(e+1,e+cnt+1,cmp); F(i,1,cnt) { if ((b[e[i].l]&b[e[i].r]).count()) { printf("%.20f\n",e[i].d/2); return 0; } b[e[i].l][e[i].r]=1; b[e[i].r][e[i].l]=1; } }
Codeforces 333E Summer Earnings ——Bitset
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。