Submission #20653

#	Time	Username	Problem	Language	Result	Execution time	Memory
20653		model_code	레이저 센서 (KOI16_laser)	C++11	100 / 100	79 ms	63152 KiB

laser

#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);
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);
                                     ^

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