Submission #404813

#	Time	Username	Problem	Language	Result	Execution time	Memory
404813		maomao90	레이저 센서 (KOI16_laser)	C++14	66 / 100	161 ms	65540 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; bool blue;
	int id;
	pt() {
		x = 0; y = 0; blue = 0; id = 0;
	}
	pt(ll x, ll y): x(x), y(y), blue(0), id(0) {}
	pt(ll x, ll y, bool blue, int id): x(x), y(y), blue(blue), 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 && blue == r.blue && 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, pt lowest) {
	points.erase(find(ALL(points), lowest));
	sort(ALL(points), [&] (pt l, pt r) {
			// sort clockwise
			return orient(lowest, l, r) < 0;
			});
	//printf("%lld %lld %d\n", lowest.x, lowest.y, lowest.id);
	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[3];
void split1(vector<pt> points, pt lowest) {
	int cnt = 0;
	pt f, s;
	int i = 0;
	REP (j, 0, 3) {
		res[j].clear();
	}
	for (pt point : points) {
		if (point.blue) {
			cnt -= 2;
		} else {
			cnt++;
		}
		if (cnt == 1 && i == 0 && !point.blue) {
			f = point;
			i++;
		} else if (cnt == 2 && i == 1 && !point.blue) {
			s = point;
			i++;
		} else {
			res[i].pb(point);
		}
	}
	ans[lowest.id] = MP(f.id, s.id);
	vector<pt> tmp[3];
	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, 3) {
		res[j].clear();
	}
	int cnt = 0;
	for (pt point : points) {
		if (point.blue) {
			cnt -= 2;
		} else {
			cnt++;
		}
		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[2];
	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;
	}
	pt lowest;
	lowest.y = INF;
	REP (i, 0, points.size()) {
		if (points[i].y < lowest.y) {
			lowest = points[i];
		}
	}
	order(points, lowest);
	if (lowest.blue) {
		split1(points, lowest);
	} else if (points[0].blue) {
		points.pb(lowest);
		lowest = points[0];
		order(points, lowest);
		split1(points, lowest);
	} else if (points.back().blue) {
		pt tmp = points.back();
		points.pb(lowest);
		lowest = tmp;
		order(points, lowest);
		split1(points, lowest);
	} else {
		split2(points, lowest);
	}
}

int main() {
	scanf("%d", &n);
	REP (i, 0, n) {
		pt temp;
		scanf("%lld%lld", &temp.x, &temp.y);
		temp.id = i;
		temp.blue = 1;
		points.pb(temp);
	}
	REP (i, n, 3 * n) {
		pt temp;
		scanf("%lld%lld", &temp.x, &temp.y);
		temp.id = i;
		temp.blue = 0;
		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 order(std::vector<pt>&, pt)':
laser.cpp:6:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
   61 |  REP (i, 0, points.size()) {
      |       ~~~~~~~~~~~~~~~~~~~               
laser.cpp:61:2: note: in expansion of macro 'REP'
   61 |  REP (i, 0, points.size()) {
      |  ^~~
laser.cpp: In function 'void solve(std::vector<pt>)':
laser.cpp:6:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
  138 |  REP (i, 0, points.size()) {
      |       ~~~~~~~~~~~~~~~~~~~               
laser.cpp:138:2: note: in expansion of macro 'REP'
  138 |  REP (i, 0, points.size()) {
      |  ^~~
laser.cpp: In function 'int main()':
laser.cpp:163:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
laser.cpp:166:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |   scanf("%lld%lld", &temp.x, &temp.y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
laser.cpp:173:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |   scanf("%lld%lld", &temp.x, &temp.y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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