Submission #46284

#	Time	Username	Problem	Language	Result	Execution time	Memory
46284		ikura355	Park (BOI16_park)	C++14	27 / 100	2560 ms	1284 KiB

park

//aiming for 58 marks
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
const double eps = 1e-7;
struct point {
	double x, y, r;
};
int n,m;
double w,h;
point p[maxn];
int head[maxn];
int bad[10], con[10][10];
double cut(point x, point y) {
	return sqrt((x.x-y.x)*(x.x-y.x) + (x.y-y.y)*(x.y-y.y));
}
bool noey(double x, double y) {
    return (y-x)>eps;
}
int findhead(int x) {
	if(head[x]==x) return x;
	return head[x] = findhead(head[x]);
}
int main() {
	scanf("%d%d%lf%lf",&n,&m,&w,&h);
	for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
	for(int tnum=1;tnum<=m;tnum++) {
		double fat; int ent;
		scanf("%lf%d",&fat,&ent); fat *= 2.0;
		for(int i=1;i<=n+4;i++) head[i] = i;
		//tree - tree
		for(int i=1;i<=n;i++) {
			for(int j=i+1;j<=n;j++) {
				if(noey(cut(p[i],p[j])-p[i].r-p[j].r, fat)) {
					head[findhead(i)] = findhead(j);
				}
			}
		}
		//tree - edge
		for(int i=1;i<=n;i++) {
			if(noey(p[i].y-p[i].r, fat)) head[findhead(i)] = findhead(n+1);
			if(noey(w-p[i].x-p[i].r, fat)) head[findhead(i)] = findhead(n+2);
			if(noey(h-p[i].y-p[i].r, fat)) head[findhead(i)] = findhead(n+3);
			if(noey(p[i].x-p[i].r, fat)) head[findhead(i)] = findhead(n+4);
		}
		//connection
		int id = 0;
		for(int i=n+1;i<=n+4;i++) {
			for(int j=i+1;j<=n+4;j++) {
				bad[++id] = findhead(i)==findhead(j);
			}
		}
        for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) con[i][j] = 1;
		if(bad[1] || bad[2] || bad[3]) con[1][2] = con[2][1] = 0;
		if(bad[2] || bad[3] || bad[4] || bad[5]) con[1][3] = con[3][1] = 0;
		if(bad[3] || bad[5] || bad[6]) con[1][4] = con[4][1] = 0;
		if(bad[1] || bad[4] || bad[5]) con[2][3] = con[3][2] = 0;
		if(bad[1] || bad[2] || bad[5] || bad[6]) con[2][4] = con[4][2] = 0;
		if(bad[2] || bad[4] || bad[6]) con[3][4] = con[4][3] = 0;
		//show
//		id = 0;
//		for(int i=1;i<=4;i++) {
//            for(int j=i+1;j<=4;j++) printf("bad %d %d = %d\n",i,j,bad[++id]);
//		}
		//answer
		for(int i=1;i<=4;i++) if(con[ent][i]) printf("%d",i);
		printf("\n");
	}
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lf%lf",&n,&m,&w,&h);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:26:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf%d",&fat,&ent); fat *= 2.0;
   ~~~~~^~~~~~~~~~~~~~~~~~~

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