#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <list>
#include <cassert>
#include <climits>
#include <chrono>
using namespace std;
#define PB push_back
#define MP make_pair
#define SZ(v) ((int)(v).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n) FORE(i,0,n)
#define FORSZ(i,a,v) FOR(i,a,SZ(v))
#define REPSZ(i,v) REP(i,SZ(v))
typedef unsigned long long ull;
typedef long long ll;
int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
struct P { int x,y,id; P():id(-1) {} P(int x,int y):x(x),y(y),id(-1) {} };
P operator-(const P &a,const P &b) { return P(a.x-b.x,a.y-b.y); }
ll operator^(const P &a,const P &b) { return (ll)a.x*b.y-(ll)a.y*b.x; }
ll side(const P &a,const P &b,const P &c) { return (b-a)^(c-a); }
void _mlt63(ull &a1,ull &a2) { // highest bits must be zero (so values less than 2^63)
ull a1h=a1>>32,a1l=a1&((1ULL<<32)-1),a2h=a2>>32,a2l=a2&((1ULL<<32)-1);
ull bh=a1h*a2h,bm=a1h*a2l+a1l*a2h,bl=a1l*a2l;
bm+=bl>>32; bl&=(1ULL<<32)-1; bh=(bh<<1)+(bm>>31); bm&=(1ULL<<31)-1;
a1=bh,a2=(bm<<32)+bl;
}
int _incirclecmp(ull a1,ull a2,ull b1,ull b2,ull c1,ull c2) { // highest bits must be zero (so values less than 2^63)
_mlt63(a1,a2); _mlt63(b1,b2); _mlt63(c1,c2);
a1+=b1; if((a2+=b2)>=(1ULL<<63)) a2-=1ULL<<63,++a1;
return a1!=c1?a1<c1?-1:+1:a2!=c2?a2<c2?-1:+1:0;
}
bool incircle(const P &a,const P &b,const P &c,const P &d) { // whether d is in circumcenter of ccw triangle abc
P aa=a-d,bb=b-d,cc=c-d;
ll u1=(ll)aa.x*aa.x+(ll)aa.y*aa.y,u2=(ll)bb.x*cc.y-(ll)bb.y*cc.x;
ll v1=(ll)bb.x*bb.x+(ll)bb.y*bb.y,v2=(ll)cc.x*aa.y-(ll)cc.y*aa.x;
ll w1=(ll)cc.x*cc.x+(ll)cc.y*cc.y,w2=(ll)aa.x*bb.y-(ll)aa.y*bb.x;
bool ret;
if(u2>0) {
if(v2>0) {
if(w2>0) ret=true;
else ret=_incirclecmp(u1,u2,v1,v2,w1,-w2)>0;
} else {
if(w2>0) ret=_incirclecmp(u1,u2,w1,w2,v1,-v2)>0;
else ret=_incirclecmp(v1,-v2,w1,-w2,u1,u2)<0;
}
} else {
if(v2>0) {
if(w2>0) ret=_incirclecmp(v1,v2,w1,w2,u1,-u2)>0;
else ret=_incirclecmp(u1,-u2,w1,-w2,v1,v2)<0;
} else {
if(w2>0) ret=_incirclecmp(u1,-u2,v1,-v2,w1,w2)<0;
else ret=false;
}
}
return ret;
}
bool operator<(const P &a,const P &b) { return a.x<b.x||a.x==b.x&&a.y<b.y; }
struct Delaunay {
int n,m;
vector<P> p;
vector<int> gprv,gnxt,gto;
void init(int _n) { n=_n,m=0; p=vector<P>(n); gprv.clear(),gnxt.clear(),gto.clear(); }
void gotobottomhulledge(int &x,int &y) {
while(gto[x]>gto[x^1]) x=gnxt[x]; while(gto[gprv[x]^1]>gto[gprv[x]]) x=gprv[x];
while(gto[y]<gto[y^1]) y=gnxt[y]; while(gto[gprv[y]^1]<gto[gprv[y]]) y=gprv[y];
while(true) {
int a=gto[x^1],b=gto[y^1];
if(side(p[a],p[b],p[gto[gprv[y]^1]])<0) y=gprv[y];
else if(side(p[a],p[b],p[gto[x]])<0) x=gnxt[x];
else break;
}
}
int addedge(int a,int x,int b,int y) { // inserts a->b before a->x in a and before b->y in b
//printf("addedge (%d,%d)-(%d,%d)\n",p[a].x,p[a].y,p[b].x,p[b].y);
gprv.PB(gprv[x]),gnxt.PB(y),gto.PB(b);
gprv.PB(gprv[y]),gnxt.PB(x),gto.PB(a);
gnxt[gprv[m+0]]=m+0,gprv[gnxt[m+0]]=m+0,gnxt[gprv[m+1]]=m+1,gprv[gnxt[m+1]]=m+1;
int ret=m; m+=2; return ret;
}
void remedge(int x) { // assumes not the last edge
//int a=gto[x^1],b=gto[x]; printf("remedge (%d,%d)-(%d,%d)\n",p[a].x,p[a].y,p[b].x,p[b].y);
gnxt[gprv[x]]=gnxt[x^1],gprv[gnxt[x]]=gprv[x^1];
gnxt[gprv[x^1]]=gnxt[x],gprv[gnxt[x^1]]=gprv[x];
gprv[x]=gnxt[x]=gto[x]=gprv[x^1]=gnxt[x^1]=gto[x^1]=-1;
}
int merge(int x,int y) {
gotobottomhulledge(x,y);
int a=gto[x^1],b=gto[y^1];
//printf("bottom hull = (%d,%d)-(%d,%d)\n",p[a].x,p[a].y,p[b].x,p[b].y);
x=addedge(a,x,b,y);
while(true) {
int ropt=-1,lopt=-1;
while(true) {
int y=gnxt[x],c=gto[y],d=gto[gnxt[y^1]];
if(side(p[a],p[b],p[c])<=0) break;
if(!incircle(p[a],p[b],p[c],p[d])) { ropt=c; break; }
remedge(y);
}
while(true) {
int y=gprv[x]^1,c=gto[y],d=gto[gprv[y]^1];
if(side(p[a],p[b],p[c])<=0) break;
if(!incircle(p[a],p[b],p[c],p[d])) { lopt=c; break; }
remedge(y^1);
}
if(lopt!=-1&&(ropt==-1||!incircle(p[a],p[b],p[lopt],p[ropt]))) {
x=addedge(lopt,gprv[x],b,gnxt[x]);
a=lopt;
} else if(ropt!=-1) {
x=addedge(a,x,ropt,gnxt[gnxt[x]]);
b=ropt;
} else {
return x;
}
}
}
int rec(int l,int r) {
int cnt=r-l+1;
if(cnt==2) {
int a=l,b=l+1;
gprv.PB(m+1),gnxt.PB(m+1),gto.PB(b);
gprv.PB(m+0),gnxt.PB(m+0),gto.PB(a);
int x=m+0; m+=2; return x;
} else if(cnt==3) {
int a=l,b=l+1,c=l+2; ll dir=side(p[a],p[b],p[c]); if(dir<0) swap(b,c),dir=-dir;
gprv.PB(m+1),gnxt.PB(m+2),gto.PB(b);
gprv.PB(m+3),gnxt.PB(m+0),gto.PB(a);
gprv.PB(m+0),gnxt.PB(m+3),gto.PB(c);
gprv.PB(m+2),gnxt.PB(m+1),gto.PB(b);
int x=m+0,y=m+3; m+=4;
if(dir>0) return addedge(a,x,c,y); else return x;
} else {
int m=l+(r-l)/2;
int x=rec(l,m);
int y=rec(m+1,r);
return merge(x,y);
}
}
int solve() {
sort(p.begin(),p.end());
return rec(0,n-1);
}
void print(int sx) {
vector<int> state(m,0); queue<int> q; state[sx]=1,q.push(sx);
while(!q.empty()) {
int x=q.front(); q.pop(); if(state[x]==2) continue;
vector<int> cur; while(state[x]!=2) { cur.PB(x); state[x]=2; x=gnxt[x]; }
REPSZ(i,cur) { int id=gto[cur[i]^1]; printf("%d=(%d,%d) ",id,p[id].x,p[id].y); } puts("");
REPSZ(i,cur) { int nx=cur[i]^1; if(state[nx]==0) state[nx]=1,q.push(nx); }
}
}
void verify(int sx) {
vector<bool> seen(m,false);
REP(i,m) if(gto[i]!=-1&&!seen[i]) {
vector<int> cur; int at=i; while(!seen[at]) { cur.PB(at); seen[at]=true; at=gnxt[at]; }
if(SZ(cur)==3) {
int a=gto[cur[0]],b=gto[cur[1]],c=gto[cur[2]];
REP(j,n) assert(!incircle(p[a],p[b],p[c],p[j]));
} else {
bool found=false; REPSZ(j,cur) if(cur[j]==sx) found=true; assert(found);
}
}
}
};
const int MAXN=50000;
int n,mod;
P p[MAXN];
int val[MAXN];
Delaunay delaunay;
vector<pair<ll,pair<int,int>>> opt;
ll calccost(const P &a,const P &b) { P d=b-a; return (ll)d.x*d.x+(ll)d.y*d.y; }
int ufpar[MAXN],ufsz[MAXN],ufmask[MAXN];
int uffind(int x) { if(ufpar[x]==x) return x; return ufpar[x]=uffind(ufpar[x]); }
void run() {
scanf("%d%d",&n,&mod);
REP(i,n) scanf("%d%d%d",&p[i].x,&p[i].y,&val[i]),p[i].id=i;
delaunay.init(n);
REP(i,n) delaunay.p[i]=p[i];
int res=delaunay.solve();
//delaunay.verify(res);
//delaunay.print(res);
opt.clear();
REP(x,delaunay.m) if(x%2==0&&delaunay.gto[x]!=-1) { int a=delaunay.p[delaunay.gto[x^1]].id,b=delaunay.p[delaunay.gto[x]].id; opt.PB(MP(calccost(p[a],p[b]),MP(a,b))); }
sort(opt.begin(),opt.end());
REP(i,n) ufpar[i]=i,ufsz[i]=i,ufmask[i]=1<<(val[i]%mod);
REPSZ(i,opt) {
int a=opt[i].second.first,b=opt[i].second.second;
//printf("%d-%d = %lf\n",a,b,sqrt(1.0*opt[i].first));
a=uffind(a),b=uffind(b); if(a==b) continue;
if(ufsz[a]<ufsz[b]) swap(a,b);
ufpar[b]=ufpar[a],ufsz[a]+=ufsz[b];
int nmask=ufmask[a]|ufmask[b]; FOR(j,1,mod) if(ufmask[b]&(1<<j)) nmask|=((ufmask[a]&((1<<(mod-j))-1))<<j)|(ufmask[a]>>(mod-j)); ufmask[a]=nmask;
if(ufmask[a]&(1<<0)) { printf("%.3lf\n",sqrt(1.0*opt[i].first)); return; }
}
assert(false);
}
int main() {
//auto start_time = chrono::high_resolution_clock::now();
run();
//fprintf(stderr,"took %d us\n",chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now()-start_time).count());
return 0;
}
Compilation message
drzava.cpp: In function 'bool operator<(const P&, const P&)':
drzava.cpp:76:65: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
bool operator<(const P &a,const P &b) { return a.x<b.x||a.x==b.x&&a.y<b.y; }
~~~~~~~~^~~~~~~~~
drzava.cpp: In member function 'void Delaunay::gotobottomhulledge(int&, int&)':
drzava.cpp:83:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(gto[x]>gto[x^1]) x=gnxt[x]; while(gto[gprv[x]^1]>gto[gprv[x]]) x=gprv[x];
^~~~~
drzava.cpp:83:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
while(gto[x]>gto[x^1]) x=gnxt[x]; while(gto[gprv[x]^1]>gto[gprv[x]]) x=gprv[x];
^~~~~
drzava.cpp:84:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(gto[y]<gto[y^1]) y=gnxt[y]; while(gto[gprv[y]^1]<gto[gprv[y]]) y=gprv[y];
^~~~~
drzava.cpp:84:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
while(gto[y]<gto[y^1]) y=gnxt[y]; while(gto[gprv[y]^1]<gto[gprv[y]]) y=gprv[y];
^~~~~
drzava.cpp: In function 'void run()':
drzava.cpp:202:6: warning: unused variable 'res' [-Wunused-variable]
int res=delaunay.solve();
^~~
drzava.cpp:197:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&mod);
~~~~~^~~~~~~~~~~~~~~~
drzava.cpp:198:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
REP(i,n) scanf("%d%d%d",&p[i].x,&p[i].y,&val[i]),p[i].id=i;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
888 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1068 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1352 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1504 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1592 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1592 KB |
Output is correct |
| 2 |
Correct |
61 ms |
9768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
9768 KB |
Output is correct |
| 2 |
Correct |
156 ms |
20028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
20028 KB |
Output is correct |
| 2 |
Correct |
152 ms |
20900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
20900 KB |
Output is correct |
| 2 |
Correct |
134 ms |
21452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
146 ms |
23252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
23252 KB |
Output is correct |
| 2 |
Correct |
166 ms |
24408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24408 KB |
Output is correct |
| 2 |
Correct |
168 ms |
25104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
25104 KB |
Output is correct |
| 2 |
Correct |
160 ms |
25996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
25996 KB |
Output is correct |
| 2 |
Correct |
168 ms |
26680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
26680 KB |
Output is correct |
| 2 |
Correct |
139 ms |
27440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
27440 KB |
Output is correct |
| 2 |
Correct |
169 ms |
28500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
28500 KB |
Output is correct |
| 2 |
Correct |
169 ms |
29272 KB |
Output is correct |
