Submission #392401

#	Time	Username	Problem	Language	Result	Execution time	Memory
392401		oolimry	레이저 센서 (KOI16_laser)	C++17	100 / 100	259 ms	63408 KiB

laser

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

const int RED = -1, BLUE = 2;

struct point{
	lint x, y, id, color;
	point operator -(point &b){ return {x-b.x, y-b.y, -2, -1}; }
};
lint cross(point a, point b){
	return (a.x*b.y - a.y*b.x);
}
lint orientation(point a, point b, point c){
	return cross(c-a,b-a);
}

vector<point> allpoints;

void reorient(vector<point> &points, int id){
	swap(points[0], points[id]);
	sort(points.begin()+1, points.end(), [&](point a, point b){
		return orientation(points[0], a, b) > 0;
	});
}

vector<int> ans[1005];
void add(point a, point b){
	if(a.color == RED) swap(a,b);
	ans[a.id].push_back(b.id);
}

void solve(vector<point> points){
	int n = sz(points);
	if(n == 0) return;
	
	sort(all(points), [&](point &a, point &b){ return ii(a.y,a.x) < ii(b.y,b.x); } );
	reorient(points, 0);
	
	//for(point p : points) show2(p.color, p.id);
	//show("FFFFFFFFFFF");
	
	if(points[0].color == RED and points[1].color == RED and points[n-1].color == RED){
		vector<point> split[2];
		int cnt = 0;
		int acc = 0;
		for(int i = 1;i < n;i++){
			point p = points[i];
			acc += p.color;
			split[cnt].push_back(p);
			
			if(cnt == 0){
				if(acc == 0){
					cnt++;
					split[1].push_back(points[0]);
				}
				else if(acc == 1){
					cnt++;
					split[0].push_back(points[0]);
				}
			}
		}
		
		solve(split[0]);
		solve(split[1]);
	}
	else{
		if(points[1].color == BLUE) reorient(points, 1);
		else if(points[n-1].color == BLUE) reorient(points, n-1);
		
		//show("HERE1");
		int acc = 0;
		int cnt = 0;
		vector<point> split[3];
		for(int i = 1;i < n;i++){
			point p = points[i];
			
			if(acc == 0 and p.color == RED and cnt < 2){
				cnt++;
				add(points[0], p);
			}
			else{
				acc += p.color;
				split[cnt].push_back(p);
			}
		}
		
		solve(split[0]);
		solve(split[1]);
		solve(split[2]);
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	for(int i = 1;i <= n;i++){
		int x, y; cin >> x >> y;
		allpoints.push_back({x,y,i,BLUE});
	}
	for(int i = 1;i <= 2*n;i++){
		int x, y; cin >> x >> y;
		allpoints.push_back({x,y,i,RED});
	}
	
	solve(allpoints);
	
	for(int i = 1;i <= n;i++){
		cout << ans[i][0] << " " << ans[i][1] << "\n";
	}
}

• Subtask 1: 14 / 14
• Subtask 2: 19 / 19
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34