| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 20652 |
2017-02-13T07:49:41 Z |
model_code |
None (KOI16_laser) |
C++11 |
|
0 ms |
1924 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1256 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1520 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1388 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1388 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1388 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1252 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1392 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1388 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1924 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1488 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1256 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1256 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
