QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#357608#2433. Panda PreserveCrysflyAC ✓1267ms4800kbC++177.5kb2024-03-19 02:22:012024-03-19 02:22:01

Judging History

你现在查看的是最新测评结果

  • [2024-03-19 02:22:01]
  • 评测
  • 测评结果:AC
  • 用时:1267ms
  • 内存:4800kb
  • [2024-03-19 02:22:01]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

typedef double db;
const db eps=1e-10,pi=3.14159265358979323846;
int sgn(db x){return x<-eps?-1:x>eps;}
int cmp(db a,db b){return sgn(a-b);}

struct P{
	db x,y;
	P(db x=0,db y=0):x(x),y(y){}
	P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
	P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
	P&operator *=(db o){return x*=o,y*=o,*this;}
	P&operator /=(db o){return x/=o,y/=o,*this;}
	friend P operator +(P a,P b){return a+=b;}
	friend P operator -(P a,P b){return a-=b;}
	friend P operator *(P a,db b){return a*=b;}
	friend P operator /(P a,db b){return a/=b;}
	friend bool operator <(P a,P b){return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;}
	friend bool operator ==(P a,P b){return cmp(a.x,b.x)==0 && cmp(a.y,b.y)==0;}
	friend db operator %(P a,P b){return a.x*b.x+a.y*b.y;} // dot
	friend db operator *(P a,P b){return a.x*b.y-a.y*b.x;} // cross
	
	P rot(db o){
		db s=sin(o),c=cos(o),xx=x*c-y*s,yy=x*s+y*c;
		x=xx,y=yy;return *this;
	}
	P rot90(){swap(x,y),x=-x;return *this;}
	db ang(){return atan2(y,x);}
	db l(){return sqrt(x*x+y*y);}
	db l2(){return x*x+y*y;}
	
	int half(){return sgn(y)==1||(sgn(y)==0&&sgn(x)>=0);}
	P unit(){return ((*this))/l();}
	
	void read(){cin>>x>>y;}
	void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
bool cmp_dir(P a,P b){
	if(a.half()!=b.half())return a.half()<b.half();
	return sgn(a*b)>0;
}

db dis(P a,P b){return (a-b).l();}
db cross(P a,P b,P c){
	// (a->b)*(a->c)
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp3(P a,P b,P c){
	return sgn(cross(a,b,c));
}

bool paral(P p1,P p2,P q1,P q2){
	// is parallel
	return sgn((p2-p1)*(q2-q1))==0;
}
P interl(P p1,P p2,P q1,P q2){
	// intersect point
	db s1=cross(q1,q2,p1),s2=-cross(q1,q2,p2);
	return (p1*s2+p2*s1)/(s1+s2);
}

bool inter(db l1,db r1,db l2,db r2){
	if(l1>r1)swap(l1,r1); if(l2>r2)swap(l2,r2);
	return !(cmp(r1,l2)==-1||cmp(r2,l1)==-1);
}
bool ismid(db a,db m,db b){
	return sgn(a-m)==0||sgn(b-m)==0||((a<m)!=(b<m));
}
bool ismid(P a,P m,P b){
	return ismid(a.x,m.x,b.x)&&ismid(a.y,m.y,b.y);
}

bool chkseg(P p1,P p2,P q1,P q2){
	return inter(p1.x,p2.x,q1.x,q2.x) && inter(p1.y,p2.y,q1.y,q2.y) &&
	cmp3(p1,p2,q1)*cmp3(p1,p2,q2)<=0 && cmp3(q1,q2,p1)*cmp3(q1,q2,p2)<=0;
}
bool chkseg_strict(P p1,P p2,P q1,P q2){
	return cmp3(p1,p2,q1)*cmp3(p1,p2,q2)<0 && cmp3(q1,q2,p1)*cmp3(q1,q2,p2)<0;
}

struct L{
	P a,b;
	L(P aa,P bb){a=aa,b=bb;}
	bool in(P p){return sgn((b-a)*(p-a))>0;}
	int in_sgn(P p){return sgn((b-a)*(p-a));}
	P dir(){return b-a;}
	bool onl(P p){
		return cmp3(a,b,p)==0;
	}
	bool onseg(P p){
		return onl(p)&&ismid(a,p,b);
	}
	bool onseg_strict(P p){
		return onl(p)&&sgn((p-a)%(a-b))*sgn((p-b)%(a-b))<0;
	}
	void out(){cout<<"("<<a.x<<","<<a.y<<")---("<<b.x<<","<<b.y<<")\n";}
};

bool chkseg(L a,L b){
	return chkseg(a.a,a.b,b.a,b.b);
}
bool paral(L a,L b){
	// is parallel
	return paral(a.a,a.b,b.a,b.b);
}
P operator &(L a,L b){
	return interl(a.a,a.b,b.a,b.b);
}
bool samedir(L a,L b){
	return paral(a,b) && sgn(a.dir()%b.dir())==1;
}
bool operator <(L a,L b){
	if(samedir(a,b)) return b.in(a.a);
	return cmp_dir(a.dir(),b.dir());
}

P proj(L a,P b){
	P d=a.dir();
	return a.a+d*((d%(b-a.a))/d.l2());
}
P reflect(L a,P b){
	return proj(a,b)*2-b;
}

db rad(P a,P b){
	return atan2l(a*b,a%b);
}

// polygon
db area(vector<P>a){
	db res=0;
	For(i,0,(int)a.size()-1)res+=a[i]*a[(i+1)%a.size()];
	return res/2;
}
int contain(vector<P>a,P p){
	int n=a.size(),res=0;
	For(i,0,n-1){
		P u=a[i],v=a[(i+1)%n];
		if(L(u,v).onseg(p))return 1;
		if(cmp(u.y,v.y)<=0)swap(u,v);
		if(cmp(p.y,u.y)>0 || cmp(p.y,v.y)<=0)continue;
		res^=cmp3(p,u,v)>0;
	}
	return res*2;
}
vector<P>cut(vector<P>a,P q1,P q2){
	vector<P>b; int n=a.size();
	For(i,0,n-1){
		P p1=a[i],p2=a[(i+1)%n];
		int d1=cmp3(q1,q2,p1),d2=cmp3(q1,q2,p2);
		if(d1>=0)b.pb(p1);
		if(d1*d2<0)b.pb(interl(p1,p2,q1,q2));
	}
	return b;
}

vector<P>convex(vector<P>a){
	int n=a.size(),m=0; if(n<=1)return a;
	sort(a.begin(),a.end());
	vector<P>st(n*2); int tp=0;
	For(i,0,n-1){
		while(tp>1 && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
		st[tp++]=a[i];
	}
	int t=tp;
	Rep(i,n-2,0){
		while(tp>t && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
		st[tp++]=a[i];
	}
	st.resize(tp-1);
	return st;
}
db diam(vector<P>a){
	int n=a.size();
	if(n<=1)return 0;
	int ii=0,jj=0;
	For(k,1,n-1){
		if(a[k]<a[ii])ii=k;
		if(a[jj]<a[k])jj=k;
	}
	int i=ii,j=jj;
	db res=dis(a[i],a[j]);
	do{
		if((a[(i+1)%n]-a[i])*(a[(j+1)%n]-a[j])>=0) (++j)%=n;
		else (++i)%=n;
		res=max(res,dis(a[i],a[j]));
	}while(i!=ii||j!=jj);
	return res;
}

bool check(L a,L b,L c){
	return c.in(a&b);
}
int checksgn(L a,L b,L c){
	return c.in_sgn(a&b);
}
vector<P>hpis(vector<L>&l){
	sort(l.begin(),l.end());
	deque<L>q;
	For(i,0,(int)l.size()-1){
		if(i&&samedir(l[i],l[i-1]))continue;
		while(q.size()>1 && !check(q[q.size()-2],q[q.size()-1],l[i]))q.pop_back();
		while(q.size()>1 && !check(q[1],q[0],l[i]))q.pop_front();
		q.pb(l[i]);
	}
	while(q.size()>2 && !check(q[q.size()-2],q[q.size()-1],q[0]))q.pop_back();
	while(q.size()>2 && !check(q[1],q[0],q[q.size()-1]))q.pop_front();
	vector<P>res;
	For(i,0,(int)q.size()-1) res.pb(q[i]&q[(i+1)%q.size()]);
	return res;
}

mt19937_64 rnd(64);

vector<L>cut(vector<L>a,L l){
	vector<L>b; int n=a.size();
	For(i,0,n-1){
		L a1=a[i],a2=a[(i+1)%n],a3=a[(i+2)%n];
		int d1=checksgn(a1,a2,l),d2=checksgn(a2,a3,l);
		if(d1>0 || d2>0 || (d1==0&&d2==0)) b.pb(a2);
		if(d1>=0 && d2<0) b.pb(l);
	}
	return b;
}

L bisector(P a,P b){
	// contain a
	P o=(a+b)*0.5;
//	L res=L(o,o+((b-a).rot90())); assert(res.in(a));
	return L(o,o+((b-a).rot90()));
}
vector<vector<L>> voronoi(vector<P>a){
	int n=a.size();
	vector<P>b=a;
	shuffle(b.begin(),b.end(),rnd);
	const db U=1e5;
	vector<vector<L>> res(n,{
		L(P(-U,-U),P(U,-U)),
		L(P(U,-U),P(U,U)),
		L(P(U,U),P(-U,U)),
		L(P(-U,U),P(-U,-U))
	});
	For(i,0,n-1){
		for(auto x:b){
			if(dis(x,a[i])>eps) res[i]=cut(res[i],bisector(a[i],x));
		}
	//	for(auto t:res[i]) t.out(); puts("---------");
	}
	return res;
}

#define maxn 400005
#define inf 0x3f3f3f3f

int n;
vector<P>a;

signed main()
{
	n=read();
	a.resize(n);
	For(i,0,n-1)a[i].read();
	auto vd=voronoi(a);
	db res=0;
	For(i,0,n-1){
		auto v=vd[i];
		int m=v.size();
		vector<P>b(m);
		For(j,0,m-1) b[j]=(v[j]&v[(j+1)%m]);
	//	For(j,0,m-1) b[j].out(); puts(";;b;;");
		for(auto x:b) if(contain(a,x)) res=max(res,dis(x,a[i]));//cout<<"chkmax "<<dis(x,a[i])<<" "<<x.x<<" "<<x.y<<" "<<a[i].x<<" "<<a[i].y<<" "<<contain(a,x)<<"\n";
		For(j,0,m-1) {
			L x=L(b[j],b[(j+1)%m]);
			For(k,0,n-1){
				L y=L(a[k],a[(k+1)%n]);
				if(!paral(x,y) && chkseg(x,y)){
					P z=(x&y);
					res=max(res,dis(z,a[i]));
				}
			}
		}
	}
	printf("%.10lf\n",res);
	return 0;
}
/*

*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4024kb

Test #2:

score: 0
Accepted
time: 0ms
memory: 3908kb

Test #3:

score: 0
Accepted
time: 0ms
memory: 3804kb

Test #4:

score: 0
Accepted
time: 0ms
memory: 3812kb

Test #5:

score: 0
Accepted
time: 1ms
memory: 3968kb

Test #6:

score: 0
Accepted
time: 1ms
memory: 3924kb

Test #7:

score: 0
Accepted
time: 1ms
memory: 4108kb

Test #8:

score: 0
Accepted
time: 0ms
memory: 3984kb

Test #9:

score: 0
Accepted
time: 0ms
memory: 4108kb

Test #10:

score: 0
Accepted
time: 0ms
memory: 3916kb

Test #11:

score: 0
Accepted
time: 0ms
memory: 4108kb

Test #12:

score: 0
Accepted
time: 0ms
memory: 3920kb

Test #13:

score: 0
Accepted
time: 1ms
memory: 3816kb

Test #14:

score: 0
Accepted
time: 0ms
memory: 3816kb

Test #15:

score: 0
Accepted
time: 0ms
memory: 3812kb

Test #16:

score: 0
Accepted
time: 0ms
memory: 3924kb

Test #17:

score: 0
Accepted
time: 1ms
memory: 3812kb

Test #18:

score: 0
Accepted
time: 0ms
memory: 3812kb

Test #19:

score: 0
Accepted
time: 0ms
memory: 3964kb

Test #20:

score: 0
Accepted
time: 0ms
memory: 4092kb

Test #21:

score: 0
Accepted
time: 0ms
memory: 3816kb

Test #22:

score: 0
Accepted
time: 1ms
memory: 3824kb

Test #23:

score: 0
Accepted
time: 1ms
memory: 3760kb

Test #24:

score: 0
Accepted
time: 1ms
memory: 4104kb

Test #25:

score: 0
Accepted
time: 1ms
memory: 3820kb

Test #26:

score: 0
Accepted
time: 0ms
memory: 3804kb

Test #27:

score: 0
Accepted
time: 0ms
memory: 3920kb

Test #28:

score: 0
Accepted
time: 0ms
memory: 3816kb

Test #29:

score: 0
Accepted
time: 0ms
memory: 3996kb

Test #30:

score: 0
Accepted
time: 0ms
memory: 3888kb

Test #31:

score: 0
Accepted
time: 1ms
memory: 3932kb

Test #32:

score: 0
Accepted
time: 1ms
memory: 3992kb

Test #33:

score: 0
Accepted
time: 0ms
memory: 4100kb

Test #34:

score: 0
Accepted
time: 0ms
memory: 3928kb

Test #35:

score: 0
Accepted
time: 1ms
memory: 4044kb

Test #36:

score: 0
Accepted
time: 1ms
memory: 4108kb

Test #37:

score: 0
Accepted
time: 1ms
memory: 3924kb

Test #38:

score: 0
Accepted
time: 0ms
memory: 3992kb

Test #39:

score: 0
Accepted
time: 0ms
memory: 3812kb

Test #40:

score: 0
Accepted
time: 1ms
memory: 4108kb

Test #41:

score: 0
Accepted
time: 1ms
memory: 3928kb

Test #42:

score: 0
Accepted
time: 0ms
memory: 3892kb

Test #43:

score: 0
Accepted
time: 0ms
memory: 3972kb

Test #44:

score: 0
Accepted
time: 1ms
memory: 4028kb

Test #45:

score: 0
Accepted
time: 1ms
memory: 4104kb

Test #46:

score: 0
Accepted
time: 1ms
memory: 4096kb

Test #47:

score: 0
Accepted
time: 0ms
memory: 3804kb

Test #48:

score: 0
Accepted
time: 0ms
memory: 3924kb

Test #49:

score: 0
Accepted
time: 0ms
memory: 3816kb

Test #50:

score: 0
Accepted
time: 1ms
memory: 3764kb

Test #51:

score: 0
Accepted
time: 1ms
memory: 3824kb

Test #52:

score: 0
Accepted
time: 3ms
memory: 3952kb

Test #53:

score: 0
Accepted
time: 50ms
memory: 4188kb

Test #54:

score: 0
Accepted
time: 194ms
memory: 4324kb

Test #55:

score: 0
Accepted
time: 3ms
memory: 3860kb

Test #56:

score: 0
Accepted
time: 66ms
memory: 3940kb

Test #57:

score: 0
Accepted
time: 265ms
memory: 4172kb

Test #58:

score: 0
Accepted
time: 3ms
memory: 3960kb

Test #59:

score: 0
Accepted
time: 63ms
memory: 4144kb

Test #60:

score: 0
Accepted
time: 260ms
memory: 4172kb

Test #61:

score: 0
Accepted
time: 2ms
memory: 3844kb

Test #62:

score: 0
Accepted
time: 47ms
memory: 4076kb

Test #63:

score: 0
Accepted
time: 188ms
memory: 4396kb

Test #64:

score: 0
Accepted
time: 1ms
memory: 3976kb

Test #65:

score: 0
Accepted
time: 0ms
memory: 3812kb

Test #66:

score: 0
Accepted
time: 0ms
memory: 3812kb

Test #67:

score: 0
Accepted
time: 0ms
memory: 4096kb

Test #68:

score: 0
Accepted
time: 760ms
memory: 4612kb

Test #69:

score: 0
Accepted
time: 0ms
memory: 4096kb

Test #70:

score: 0
Accepted
time: 775ms
memory: 4452kb

Test #71:

score: 0
Accepted
time: 50ms
memory: 4068kb

Test #72:

score: 0
Accepted
time: 691ms
memory: 4548kb

Test #73:

score: 0
Accepted
time: 132ms
memory: 4260kb

Test #74:

score: 0
Accepted
time: 689ms
memory: 4456kb

Test #75:

score: 0
Accepted
time: 183ms
memory: 4176kb

Test #76:

score: 0
Accepted
time: 9ms
memory: 3948kb

Test #77:

score: 0
Accepted
time: 9ms
memory: 4016kb

Test #78:

score: 0
Accepted
time: 9ms
memory: 4156kb

Test #79:

score: 0
Accepted
time: 9ms
memory: 3864kb

Test #80:

score: 0
Accepted
time: 9ms
memory: 3824kb

Test #81:

score: 0
Accepted
time: 9ms
memory: 4084kb

Test #82:

score: 0
Accepted
time: 10ms
memory: 4052kb

Test #83:

score: 0
Accepted
time: 6ms
memory: 4048kb

Test #84:

score: 0
Accepted
time: 9ms
memory: 4052kb

Test #85:

score: 0
Accepted
time: 9ms
memory: 3872kb

Test #86:

score: 0
Accepted
time: 4ms
memory: 3976kb

Test #87:

score: 0
Accepted
time: 9ms
memory: 3876kb

Test #88:

score: 0
Accepted
time: 9ms
memory: 3856kb

Test #89:

score: 0
Accepted
time: 9ms
memory: 3996kb

Test #90:

score: 0
Accepted
time: 9ms
memory: 4080kb

Test #91:

score: 0
Accepted
time: 9ms
memory: 3980kb

Test #92:

score: 0
Accepted
time: 810ms
memory: 4312kb

Test #93:

score: 0
Accepted
time: 747ms
memory: 4352kb

Test #94:

score: 0
Accepted
time: 2ms
memory: 3960kb

Test #95:

score: 0
Accepted
time: 3ms
memory: 4136kb

Test #96:

score: 0
Accepted
time: 8ms
memory: 3872kb

Test #97:

score: 0
Accepted
time: 7ms
memory: 3880kb

Test #98:

score: 0
Accepted
time: 1240ms
memory: 4792kb

Test #99:

score: 0
Accepted
time: 1267ms
memory: 4692kb

Test #100:

score: 0
Accepted
time: 1256ms
memory: 4508kb

Test #101:

score: 0
Accepted
time: 1259ms
memory: 4800kb

Test #102:

score: 0
Accepted
time: 1226ms
memory: 4612kb

Test #103:

score: 0
Accepted
time: 968ms
memory: 4492kb

Test #104:

score: 0
Accepted
time: 1191ms
memory: 4688kb