oj.uz

Submission #135523

# Submission time Handle Problem Language Result Execution time Memory
135523 2019-07-24T07:31:01 Z junodeveloper None (KOI16_laser) C++14
19 / 100
 3 ms 504 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
struct point {
	int x, y, f, i;
} p[3010];
int n, ans[1010][2];
ll cross(const point& a,const point& b,const point& c) {
	return (ll)(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void solve(int l, int r) {
	if(r-l+1<3) return;
	if(r-l+1==3) {
		int i,j,k=0;
		for(i=l;i<=r;i++) if(p[i].f==2)
			for(j=l;j<=r;j++)
				if(i!=j) ans[p[i].i][k++]=p[j].i;
		return;
	}
	int j=-1;
	int i;
	for(i=l;i<=r;i++)
		if(j==-1||p[i].x<p[j].x||(p[i].x==p[j].x&&p[i].y<p[j].y)) j=i;
	swap(p[j],p[l]);
	sort(p+l+1,p+r+1,[&](const point& a,const point& b) {
		return cross(p[l], a, b)>0;
	});
	if(p[l].f==-1 && (p[l+1].f==2||p[r].f==2)) {
		if(p[l+1].f==2) swap(p[l], p[l+1]);
		else swap(p[l], p[r]);
		sort(p+l+1,p+r+1,[&](const point& a,const point& b) {
			return cross(p[l], a, b)>0;
		});
	}
	int sum=p[l].f;
	for(i=l+1;i<=r;i++){
		sum+=p[i].f;
		if(!sum) {
			if(p[l].f==2) {
				ans[p[l].i][0]=p[i].i;
				ans[p[l].i][1]=p[i-1].i;
				solve(l+1,i-2);
				solve(i+1,r);
				return;
			} else {
				if(i<r) {
					solve(l,i);
					solve(i+1,r);
					return;
				} else {
					sum=p[l].f;
					for(j=r;j>l;j--) {
						sum+=p[j].f;
						if(!sum) {
							swap(p[l],p[j-1]);
							solve(l,j-2);
							solve(j-1,r);
							return;
						}
					}
				}
			}
		}
	}
}
int main() {
	scanf("%d",&n);
	for(int i=0;i<n;i++) {
		scanf("%d%d",&p[i].x,&p[i].y);
		p[i].f=2; p[i].i=i;
	}
	for(int i=0;i<n+n;i++) {
		scanf("%d%d",&p[n+i].x,&p[n+i].y);
		p[n+i].f=-1; p[n+i].i=i;
	}
	solve(0,3*n-1);
	for(int i=0;i<n;i++) printf("%d %d\n",ans[i][0]+1,ans[i][1]+1);
	return 0;
}

Compilation message

laser.cpp: In function 'int main()':
laser.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
laser.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p[i].x,&p[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
laser.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p[n+i].x,&p[n+i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -