Submission #39793

#	Time	Username	Problem	Language	Result	Execution time	Memory
39793		nonocut	Park (BOI16_park)	C++14	0 / 100	322 ms	55236 KiB

park

#include<bits/stdc++.h>
using namespace std;

struct point {
	double x, y, r;
};

struct quest {
	int id, e;
	double r;
};

int n,m;
double H,W;
point p[2010];
quest q[100005];
vector<pair<double,pair<int,int> > > edge;
int head[2010];
vector<int> ans[100005];

int get(int x) {
	if(x==head[x]) return x;
	return head[x] = get(head[x]);
}

bool cmp(quest a, quest b) {
	return a.r < b.r;
}

int main() {
	int i,j,x;
	double temp;

	scanf("%d%d%lf%lf",&n,&m,&W,&H);
	n += 4;
	for(i=5;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
	for(i=1;i<=m;i++) scanf("%lf%d",&q[i].r,&q[i].e), q[i].id = i;

	//point to point
	for(i=5;i<=n;i++) {
		for(j=i+1;j<=n;j++) {
			temp = (sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x) + (p[i].y-p[j].y)*(p[i].y-p[j].y)) - p[i].r - p[j].r)/2.0;
			edge.push_back({temp, {i,j}});
//			printf("point to point %d - %d is required at least %lf\n",i,j,temp);
		}
	}
	//point to edge
	for(i=5;i<=n;i++) {
		temp = p[i].x - p[i].r;
		edge.push_back({temp, {1,i}});
		temp = p[i].y - p[i].r;
		edge.push_back({temp, {2,i}});
		temp = (W - p[i].x) - p[i].r;
		edge.push_back({temp, {3,i}});
		temp = (H - p[i].y) - p[i].r;
		edge.push_back({temp, {4,i}});
	}

	sort(edge.begin(),edge.end());
	sort(&q[1],&q[m+1],cmp);

	for(i=1;i<=n;i++) head[i] = i;

	for(i=1,j=0;i<=m;i++) {
		while(j<edge.size()) {
			if(edge[j].first>=q[i].r) break;
//			printf("edge %d - %d\n",edge[j].second.first,edge[j].second.second);
			head[get(edge[j].second.first)] = get(edge[j].second.second);
			++j;
		}
//		printf("------------------- quest %d\n",q[i].id);
		for(x=1;x<=4;x++) {
            if(q[i].e == x) ans[q[i].id].push_back(x);
            else if(get(q[i].e)!=get(q[i].e%4 + 1)) {
                if((x+q[i].e)%2==0) {
                    if(get(x)!=get(x%4+1) && get(1)!=get(3) && get(2)!=get(4)) ans[q[i].id].push_back(x);
                }
                else {
                    if(q[i].e + x == 5) {
                        if(get(x)!=get(x%4+1) && get(1)!=get(3)) ans[q[i].id].push_back(x);
                    }
                    else {
                        if(get(x)!=get(x%4+1) && get(2)!=get(4)) ans[q[i].id].push_back(x);
                    }
                }
            }
		}
	}

	for(i=1;i<=m;i++) {
		for(j=0;j<ans[i].size();j++) printf("%d",ans[i][j]);
		printf("\n");
	}
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:65:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<edge.size()) {
          ^
park.cpp:91:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<ans[i].size();j++) printf("%d",ans[i][j]);
            ^
park.cpp:34:33: 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:36:62: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=5;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
                                                              ^
park.cpp:37:63: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=m;i++) scanf("%lf%d",&q[i].r,&q[i].e), q[i].id = i;
                                                               ^

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