Submission #20652

#TimeUsernameProblemLanguageResultExecution timeMemory
20652model_code레이저 센서 (KOI16_laser)C++11
19 / 100
0 ms1924 KiB
#include <stdio.h> #include <stdlib.h> #include <algorithm> #include <vector> #include <cassert> using namespace std; struct point { point() { x = y = t = 0; } point(long long x_, long long y_, int t_) { x = x_; y = y_; t = t_; } long long x, y; int t; bool operator <(const point &t) const { return x * t.y > y * t.x; } point operator -(point &a) { return point(x - a.x, y - a.y, t); } }P[3020]; int R[1020][2]; int ccw(point &a, point &b, point &c) { long long p = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y); if (p > 0) return 1; if (p < 0) return -1; return 0; } int ccw(int i, int j, int k) { return ccw(P[i], P[j], P[k]); } void match(vector<int> &p) { if (p.empty()) return; vector<point> u; for (int i = 0; i < p.size(); i++) { u.push_back(P[p[i]]); u.back().t = p[i]; } for (int i = 1; i < u.size(); i++) { if (u[0].y > u[i].y || (u[0].y == u[i].y && u[0].x > u[i].x)) { swap(u[0], u[i]); } } for (int i = (int)u.size() - 1; i >= 0; i--) u[i] = u[i] - u[0]; sort(u.begin() + 1, u.end()); int s = -1, f = u[0].t; u.erase(u.begin()); if (P[f].t) s = f; else if (P[u[0].t].t) s = u[0].t; else if (P[u.back().t].t) s = u.back().t; if (s != -1) { if (s != f) { u.clear(); for (int i = 0; i < p.size(); i++) if (p[i] != s) { u.push_back(P[p[i]] - P[s]); u.back().t = p[i]; } sort(u.begin(), u.end()); } int b = 0, obj = -1; vector<int> g; for (int j = 0; j < u.size(); j++) { b += P[u[j].t].t ? +2 : -1; if (b == obj) { R[s][-obj - 1] = u[j].t; match(g); g.clear(); obj--; if (obj < -2) obj = -2000000; } else { g.push_back(u[j].t); } } match(g); return; } for (int k = 0; k < 2; k++) { int b = 0; vector<int> g; for (int j = 0; j < u.size(); j++) { b += P[u[j].t].t ? +2 : -1; g.push_back(u[j].t); if (b == 0) { match(g); g.clear(); for (int i = j + 1; i < u.size(); i++) g.push_back(u[i].t); g.push_back(f); match(g); return; } } reverse(u.begin(), u.end()); } } int main() { int N; scanf("%d", &N); vector<int> pt; for (int i = 0; i < N * 3; i++) { scanf("%lld %lld", &P[i].x, &P[i].y); assert(P[i].y == P[i].x * P[i].x); P[i].t = i < N; pt.push_back(i); } match(pt); for (int i = 0; i < N; i++) printf("%d %d\n", R[i][0] - N + 1, R[i][1] - N + 1); return 0; }

Compilation message (stderr)

laser.cpp: In function 'void match(std::vector<int>&)':
laser.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (int i = 0; i < p.size(); i++) {
                   ^
laser.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (int i = 1; i < u.size(); i++) {
                   ^
laser.cpp:65:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (int i = 0; i < p.size(); i++) if (p[i] != s) {
                   ^
laser.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (int j = 0; j < u.size(); j++) {
                   ^
laser.cpp:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (int j = 0; j < u.size(); j++) {
                   ^
laser.cpp:103:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (int i = j + 1; i < u.size(); i++) g.push_back(u[i].t);
                       ^
laser.cpp: In function 'int main()':
laser.cpp:115:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 int N; scanf("%d", &N);
                       ^
laser.cpp:119:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%lld %lld", &P[i].x, &P[i].y);
                                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...