| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 486440 |
2021-11-11T16:50:20 Z |
rainboy |
Relay (COI16_relay) |
C |
|
2000 ms |
2792 KB |
#include <stdio.h>
#define N 100000
#define M 100000
long long cross2(int x1, int y1, int x2, int y2) {
return (long long) x1 * y2 - (long long) x2 * y1;
}
long long cross(int x0, int y0, int x1, int y1, int x2, int y2) {
return cross2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}
int xx[N + M], yy[N + M], xxl[N], yyl[N], xxr[N], yyr[N];
int compare(int x1, int y1, int x2, int y2) {
int sgn1 = x1 < 0 || x1 == 0 && y1 < 0 ? -1 : 1;
int sgn2 = x2 < 0 || x2 == 0 && y2 < 0 ? -1 : 1;
long long c;
if (sgn1 != sgn2)
return sgn1 - sgn2;
c = cross2(x1, y1, x2, y2);
return c == 0 ? 0 : (c > 0 ? -1 : 1);
}
int visible(int i1, int i2) {
int xl1 = xxl[i1], yl1 = yyl[i1], xr1 = xxr[i1], yr1 = yyr[i1];
int xl2 = xxl[i2], yl2 = yyl[i2], xr2 = xxr[i2], yr2 = yyr[i2];
int l1r1 = compare(xl1, yl1, xr1, yr1) <= 0;
int r1l2 = compare(xr1, yr1, xl2, yl2) < 0;
int l2r2 = compare(xl2, yl2, xr2, yr2) <= 0;
int r2l1 = compare(xr2, yr2, xl1, yl1) < 0;
return !(l1r1 && r1l2 && l2r2 || r1l2 && l2r2 && r2l1 || l2r2 && r2l1 && l1r1 || r2l1 && l1r1 && r1l2);
}
int main() {
static char good[N];
int n, m, i, i1, i2, j, p, q, k;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[i], &yy[i]);
scanf("%d", &m);
for (j = 0; j < m; j++)
scanf("%d%d", &xx[n + j], &yy[n + j]);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++) {
p = (j - 1 + m) % m, q = (j + 1) % m;
if (cross(xx[i], yy[i], xx[n + p], yy[n + p], xx[n + j], yy[n + j]) >= 0
&& cross(xx[i], yy[i], xx[n + q], yy[n + q], xx[n + j], yy[n + j]) > 0)
xxl[i] = xx[i] - xx[n + j], yyl[i] = yy[i] - yy[n + j];
if (cross(xx[i], yy[i], xx[n + q], yy[n + q], xx[n + j], yy[n + j]) <= 0
&& cross(xx[i], yy[i], xx[n + p], yy[n + p], xx[n + j], yy[n + j]) < 0)
xxr[i] = xx[n + j] - xx[i], yyr[i] = yy[n + j] - yy[i];
}
for (i1 = 1; i1 < n; i1++)
if (visible(0, i1)) {
good[i1] = 1;
for (i2 = 1; i2 < n; i2++)
if (visible(i1, i2))
good[i2] = 1;
}
k = 0;
for (i = 1; i < n; i++)
if (good[i])
k++;
printf("%d\n", k);
return 0;
}
Compilation message
relay.c: In function 'compare':
relay.c:17:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
17 | int sgn1 = x1 < 0 || x1 == 0 && y1 < 0 ? -1 : 1;
| ~~~~~~~~^~~~~~~~~
relay.c:18:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
18 | int sgn2 = x2 < 0 || x2 == 0 && y2 < 0 ? -1 : 1;
| ~~~~~~~~^~~~~~~~~
relay.c: In function 'visible':
relay.c:35:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
35 | return !(l1r1 && r1l2 && l2r2 || r1l2 && l2r2 && r2l1 || l2r2 && r2l1 && l1r1 || r2l1 && l1r1 && r1l2);
| ~~~~~~~~~~~~~^~~~~~~
relay.c:35:72: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
35 | return !(l1r1 && r1l2 && l2r2 || r1l2 && l2r2 && r2l1 || l2r2 && r2l1 && l1r1 || r2l1 && l1r1 && r1l2);
| ~~~~~~~~~~~~~^~~~~~~
relay.c:35:96: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
35 | return !(l1r1 && r1l2 && l2r2 || r1l2 && l2r2 && r2l1 || l2r2 && r2l1 && l1r1 || r2l1 && l1r1 && r1l2);
| ~~~~~~~~~~~~~^~~~~~~
relay.c: In function 'main':
relay.c:42:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
relay.c:44:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relay.c:45:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%d", &m);
| ^~~~~~~~~~~~~~~
relay.c:47:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d%d", &xx[n + j], &yy[n + j]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
3 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
3 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
111 ms |
476 KB |
Output is correct |
| 12 |
Correct |
115 ms |
476 KB |
Output is correct |
| 13 |
Correct |
67 ms |
448 KB |
Output is correct |
| 14 |
Correct |
119 ms |
452 KB |
Output is correct |
| 15 |
Correct |
63 ms |
440 KB |
Output is correct |
| 16 |
Correct |
81 ms |
460 KB |
Output is correct |
| 17 |
Correct |
69 ms |
576 KB |
Output is correct |
| 18 |
Correct |
99 ms |
460 KB |
Output is correct |
| 19 |
Correct |
44 ms |
448 KB |
Output is correct |
| 20 |
Correct |
45 ms |
452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
3 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Execution timed out |
2060 ms |
2792 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
3 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
111 ms |
476 KB |
Output is correct |
| 12 |
Correct |
115 ms |
476 KB |
Output is correct |
| 13 |
Correct |
67 ms |
448 KB |
Output is correct |
| 14 |
Correct |
119 ms |
452 KB |
Output is correct |
| 15 |
Correct |
63 ms |
440 KB |
Output is correct |
| 16 |
Correct |
81 ms |
460 KB |
Output is correct |
| 17 |
Correct |
69 ms |
576 KB |
Output is correct |
| 18 |
Correct |
99 ms |
460 KB |
Output is correct |
| 19 |
Correct |
44 ms |
448 KB |
Output is correct |
| 20 |
Correct |
45 ms |
452 KB |
Output is correct |
| 21 |
Execution timed out |
2060 ms |
2792 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
