Submission #404829

#	Time	Username	Problem	Language	Result	Execution time	Memory
404829		maomao90	레이저 센서 (KOI16_laser)	C++14	100 / 100	219 ms	48196 KiB

laser

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

#define mnto(x, y) x = min(x, (__typeof__(x)) y)
#define mxto(x, y) x = max(x, (__typeof__(x)) y)
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ii> vii;

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 3005

struct pt {
	ll x, y; int color;
	int id;
	pt() {
		x = 0; y = 0; color = 0; id = 0;
	}
	pt(ll x, ll y): x(x), y(y), color(0), id(0) {}
	pt(ll x, ll y, int color, int id): x(x), y(y), color(color), id(id) {}
	pt operator-(const pt& other) const {
		return pt(x - other.x, y - other.y);
	}
	bool operator==(const pt& r) const {
		return x == r.x && y == r.y && color == r.color && id == r.id;
	}
};
ll cross(pt a, pt b) {
	return a.x * b.y - a.y * b.x;
}
// positive if c is to the right/top of line ab
ll orient(pt a, pt b, pt c) {
	return cross(b - a, c - a);
}

int n;
vector<pt> points;
ii ans[MAXN];

void order(vector<pt>& points) {
	sort(points.begin() + 1, points.end(), [&] (pt l, pt r) {
			// sort clockwise
			return orient(points[0], l, r) < 0;
			});
	//REP (i, 0, points.size()) {
		//printf(" %lld %lld %d\n", points[i].x, points[i].y, points[i].id);
	//}
}

void solve(vector<pt> points);

vector<pt> res[5];
void split1(vector<pt> points, pt lowest) {
	int cnt = 0;
	pt f, s;
	int i = 0;
	REP (j, 0, 5) {
		res[j].clear();
	}
	for (pt point : points) {
		cnt += point.color;
		if (cnt == -1 && i == 0 && point.color == -1) {
			f = point;
			i++;
		} else if (cnt == -2 && i == 1 && point.color == -1) {
			s = point;
			i++;
		} else {
			res[i].pb(point);
		}
	}
	ans[lowest.id] = MP(f.id, s.id);
	vector<pt> tmp[5];
	REP (j, 0, 3) {
		tmp[j] = res[j];
	}
	REP (j, 0, 3) {
		solve(tmp[j]);
	}
}

void split2(vector<pt> points, pt lowest) {
	int i = 0;
	REP (j, 0, 5) {
		res[j].clear();
	}
	int cnt = 0;
	for (pt point : points) {
		cnt += point.color;
		res[i].pb(point);
		if (i == 0 && cnt == 0) {
			i++;
			res[i].pb(lowest);
		} else if (i == 0 && cnt == 1) {
			res[i].pb(lowest);
			i++;
		}
	}
	vector<pt> tmp[5];
	REP (j, 0, 2) {
		tmp[j] = res[j];
	}
	REP (j, 0, 2) {
		solve(tmp[j]);
	}
}

void solve(vector<pt> points) {
	if (points.size() == 0) {
	   	return;
	}
	sort(ALL(points), [&] (pt l, pt r) {
			return l.y < r.y;
			});
	order(points);
	if (points[0].color == 2 || points[1].color == 2 || points.back().color == 2) {
		if (points[1].color == 2) {
			swap(points[1], points[0]);
		} else if (points.back().color == 2) {
			swap(points[points.size() - 1], points[0]);
		}
		order(points);
		int cnt = 0;
		pt f, s;
		int i = 0;
		vector<pt> res[5];
		for (int j = 1; j < points.size(); j++) {
			pt point = points[j];
			cnt += point.color;
			if (cnt == -1 && i == 0 && point.color == -1) {
				f = point;
				i++;
			} else if (cnt == -2 && i == 1 && point.color == -1) {
				s = point;
				i++;
			} else {
				res[i].pb(point);
			}
		}
		ans[points[0].id] = MP(f.id, s.id);
		REP (j, 0, 3) {
			solve(res[j]);
		}
	} else {
		int i = 0;
		int cnt = 0;
		vector<pt> res[5];
		for (int j = 1; j < points.size(); j++) {
			pt point = points[j];
			cnt += point.color;
			res[i].pb(point);
			if (i == 0 && cnt == 0) {
				i++;
				res[i].pb(points[0]);
			} else if (i == 0 && cnt == 1) {
				res[i].pb(points[0]);
				i++;
			}
		}
		REP (j, 0, 2) {
			solve(res[j]);
		}
	}
}

int main() {
	scanf("%d", &n);
	REP (i, 0, n) {
		pt temp;
		scanf("%lld%lld", &temp.x, &temp.y);
		temp.id = i;
		temp.color = 2;
		points.pb(temp);
	}
	REP (i, n, 3 * n) {
		pt temp;
		scanf("%lld%lld", &temp.x, &temp.y);
		temp.id = i;
		temp.color = -1;
		points.pb(temp);
	}
	solve(points);
	REP (i, 0, n) {
		printf("%d %d\n", ans[i].FI - n + 1, ans[i].SE - n + 1);
	}
	return 0;
}

Compilation message (stderr)

laser.cpp: In function 'void solve(std::vector<pt>)':
laser.cpp:141:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   for (int j = 1; j < points.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
laser.cpp:162:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |   for (int j = 1; j < points.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
laser.cpp: In function 'int main()':
laser.cpp:181:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
laser.cpp:184:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |   scanf("%lld%lld", &temp.x, &temp.y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
laser.cpp:191:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |   scanf("%lld%lld", &temp.x, &temp.y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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