Submission #135534

#	Time	Username	Problem	Language	Result	Execution time	Memory
135534		junodeveloper	레이저 센서 (KOI16_laser)	C++14	100 / 100	137 ms	636 KiB

laser

#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)-(ll)(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 (stderr)

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: 14 / 14
• Subtask 2: 19 / 19
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34