Submission #647498

#	Time	Username	Problem	Language	Result	Execution time	Memory
647498		rsjw	Park (BOI16_park)	C++17	100 / 100	694 ms	64676 KiB

park

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define double long double
struct point {
	int x,y,r;
} a[2010];
int f[2010];
int N,T,n,m;
double D(point i,point j) {
	return sqrt((double)(i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y))-i.r-j.r;
}
struct edge {
	int i,j;
	double d;
} b[4004010];
bool cmp(edge a,edge b) {
	return a.d<b.d;
}
int find(int x) {
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void uni(int x,int y) {
	f[find(x)]=find(y);
}
int check(int x,int y) {
	return find(x)==find(y);
}
double r[5][5];
bool ud() {
	return check(N+1,N+2);
}
bool ul() {
	return check(N+1,N+3);
}
bool ur() {
	return check(N+1,N+4);
}
bool dl() {
	return check(N+2,N+3);
}
bool dr() {
	return check(N+2,N+4);
}
bool lr() {
	return check(N+3,N+4);
}
//N+1 UpLim,N+2 DoLim,N+3 LeLim,N+4 RiLim
int l;
using namespace std;
signed main() {
	int i,j;
	scanf("%lld%lld%lld%lld",&N,&T,&n,&m);
	for(i=1; i<=N; i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].r);
	for(i=1; i<=N; i++) for(j=i+1; j<=N; j++) b[++l]= (edge) {
			i,j,D(a[i],a[j])
		};
	for(i=1; i<=N; i++) b[++l]= (edge) {i,N+1,(double)m-a[i].y-a[i].r},b[++l]= (edge) {i,N+2,(double)a[i].y-a[i].r},b[++l]= (edge) {i,N+3,(double)a[i].x-a[i].r},b[++l]= (edge) {
		i,N+4,(double)n-a[i].x-a[i].r
	};
	sort(b+1,b+l+1,cmp);
	for(i=1; i<=N+4; i++) f[i]=i;
	for(i=1; i<=4; i++)for(j=1; j<=4; j++) r[i][j]=2e10;
	for(i=1; i<=l; i++) {
		uni(b[i].i,b[i].j);
		if((dl()||dr()||ud())&&fabs(r[1][2]-2e10)<1e-2) r[1][2]=b[i].d;
		if((dl()||ur()||ud()||lr())&&fabs(r[1][3]-2e10)<1e-2) r[1][3]=b[i].d;
		if((dl()||ul()||lr())&&fabs(r[1][4]-2e10)<1e-2) r[1][4]=b[i].d;
		if((dr()||ur()||lr())&&fabs(r[2][3]-2e10)<1e-2) r[2][3]=b[i].d;
		if((ul()||dr()||lr()||ud())&&fabs(r[2][4]-2e10)<1e-2) r[2][4]=b[i].d;
		if((ul()||ur()||ud())&&fabs(r[3][4]-2e10)<1e-2) r[3][4]=b[i].d;
	}
	for(i=1; i<=4; i++) for(j=1; j<i; j++) r[i][j]=r[j][i];
	while(T--) {
		scanf("%lld%lld",&n,&m);
		for(i=1; i<=4; i++) if(r[m][i]>=2*n) printf("%lld",i);
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%lld%lld%lld%lld",&N,&T,&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:55:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  for(i=1; i<=N; i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].r);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%lld%lld",&n,&m);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42