| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 924360 |
2024-02-08T22:28:02 Z |
rainboy |
None (KOI16_laser) |
C |
|
1 ms |
348 KB |
/* https://math.stackexchange.com/questions/4650848/prove-that-if-2n-points-are-colored-red-or-blue-then-we-can-always-connect-th */
#include <stdio.h>
#include <string.h>
#define N 1000
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[N * 4], yy[N * 4], uu[N], vv[N], n, o;
long long cross(int i, int j, int k) {
return (long long) (xx[j] - xx[i]) * (yy[k] - yy[i]) - (long long) (xx[k] - xx[i]) * (yy[j] - yy[i]);
}
int compare(int i, int j) {
long long c;
if (xx[i] == xx[j] && yy[i] == yy[j])
return 0;
if (xx[i] == xx[o] && yy[i] == yy[o])
return -1;
if (xx[j] == xx[o] && yy[j] == yy[o])
return 1;
c = cross(o, i, j);
return c < 0 ? -1 : 1;
}
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
long long c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
void solve(int *ii, int m) {
int h, h_, i, j, tmp, d;
if (m == 2) {
if (ii[0] >= n * 2)
tmp = ii[0], ii[0] = ii[1], ii[1] = tmp;
i = ii[0] >> 1, j = ii[1] - n * 2;
if (uu[i] == -1)
uu[i] = j;
else
vv[i] = j;
return;
}
h_ = -1;
for (h = 0; h < m; h++)
if (h_ == -1 || xx[ii[h_]] > xx[ii[h]] || xx[ii[h_]] == xx[ii[h]] && yy[ii[h_]] > yy[ii[h]])
h_ = h;
o = ii[h_];
tmp = ii[0], ii[0] = ii[h_], ii[h_] = tmp;
sort(ii, 1, m);
d = ii[0] < n * 2 ? 1 : -1;
for (h = 1; h + 1 < m; h++)
if ((d += ii[h] < n * 2 ? 1 : -1) == 0) {
solve(ii, h + 1), solve(ii + h + 1, m - h - 1);
return;
}
tmp = ii[1], ii[1] = ii[m - 1], ii[m - 1] = tmp;
solve(ii, 2), solve(ii + 2, m - 2);
}
int main() {
static int ii[N * 4];
int i, x, y;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d%d", &x, &y);
xx[i << 1 | 0] = x, yy[i << 1 | 0] = y;
xx[i << 1 | 1] = x, yy[i << 1 | 1] = y;
}
for (i = 0; i < n * 2; i++)
scanf("%d%d", &xx[n * 2 + i], &yy[n * 2 + i]);
for (i = 0; i < n * 4; i++)
ii[i] = i;
memset(uu, -1, n * sizeof *uu), memset(vv, -1, n * sizeof *vv);
solve(ii, n * 4);
for (i = 0; i < n; i++)
printf("%d %d\n", uu[i] + 1, vv[i] + 1);
for (i = 0; i < n; i++) {
printf("%d %d %d %d\n", xx[i << 1 | 0], yy[i << 1 | 0], xx[n * 2 + uu[i]], yy[n * 2 + uu[i]]);
printf("%d %d %d %d\n", xx[i << 1 | 1], yy[i << 1 | 1], xx[n * 2 + vv[i]], yy[n * 2 + vv[i]]);
}
return 0;
}
Compilation message
laser.c: In function 'solve':
laser.c:69:69: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
69 | if (h_ == -1 || xx[ii[h_]] > xx[ii[h]] || xx[ii[h_]] == xx[ii[h]] && yy[ii[h_]] > yy[ii[h]])
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
laser.c: In function 'main':
laser.c:88:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
laser.c:90:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | scanf("%d%d", &x, &y);
| ^~~~~~~~~~~~~~~~~~~~~
laser.c:95:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf("%d%d", &xx[n * 2 + i], &yy[n * 2 + i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Expected EOF |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Expected EOF |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Expected EOF |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Expected EOF |
| 2 |
Halted |
0 ms |
0 KB |
- |
