| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 485916 |
2021-11-09T17:44:08 Z |
rainboy |
SIR (COI15_sir) |
C |
|
213 ms |
5392 KB |
#include <stdio.h>
#define N 300000
#define M 300000
long long max(long long a, long long b) { return a > b ? a : b; }
long long cross2(int x1, int y1, int x2, int y2) {
return (long long) x1 * y2 - (long long) x2 * y1;
}
int xx[N + M], yy[N + M];
long long cross(int i, int j, int k) {
return cross2(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int o;
int compare(int i, int j) {
long long c = cross(o, i, j);
if (c != 0)
return c < 0 ? -1 : 1;
if (xx[i] != xx[j])
return xx[i] < xx[j] ? -1 : 1;
if (yy[i] != yy[j])
return yy[i] < yy[j] ? -1 : 1;
return 0;
}
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) {
int 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;
}
}
int main() {
static int jj[M];
int n, m, cnt, i, i1, i2, j;
long long ans, area;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[n - 1 - i], &yy[n - 1 - i]);
scanf("%d", &m);
for (j = 0; j < m; j++)
scanf("%d%d", &xx[n + j], &yy[n + j]);
o = -1;
for (j = 0; j < m; j++)
if (o == -1 || xx[o] > xx[n + j] || xx[o] == xx[n + j] && yy[o] > yy[n + j])
o = n + j;
for (j = 0; j < m; j++)
jj[j] = n + j;
jj[0] = o, jj[o - n] = n + 0;
sort(jj, 1, m);
cnt = 0;
for (j = 0; j < m; j++) {
while (cnt >= 2 && cross(jj[cnt - 2], jj[cnt - 1], jj[j]) >= 0)
cnt--;
jj[cnt++] = jj[j];
}
ans = 0, area = 0;
for (i1 = 0, i2 = 0, j = 0; i1 < n; i1++) {
while (cross(i1, jj[j], jj[(j + 1) % cnt]) > 0)
j = (j + 1) % cnt;
while (cross(i1, jj[j], jj[(j - 1 + cnt) % cnt]) > 0)
j = (j - 1 + cnt) % cnt;
while (cross(i1, jj[j], (i2 + 1) % n) > 0) {
area -= cross2(xx[i2], yy[i2], xx[(i2 + 1) % n], yy[(i2 + 1) % n]);
i2 = (i2 + 1) % n;
}
ans = max(ans, area - cross2(xx[i2], yy[i2], xx[i1], yy[i1]));
area += cross2(xx[i1], yy[i1], xx[(i1 + 1) % n], yy[(i1 + 1) % n]);
}
printf("%lld\n", ans);
return 0;
}
Compilation message
sir.c: In function 'main':
sir.c:73:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
73 | if (o == -1 || xx[o] > xx[n + j] || xx[o] == xx[n + j] && yy[o] > yy[n + j])
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
sir.c:65:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
sir.c:67:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d%d", &xx[n - 1 - i], &yy[n - 1 - i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sir.c:68:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d", &m);
| ^~~~~~~~~~~~~~~
sir.c:70:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d%d", &xx[n + j], &yy[n + j]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
213 ms |
5392 KB |
Output is correct |
| 2 |
Correct |
195 ms |
5248 KB |
Output is correct |
| 3 |
Correct |
158 ms |
4328 KB |
Output is correct |
| 4 |
Correct |
43 ms |
1352 KB |
Output is correct |
| 5 |
Correct |
164 ms |
4144 KB |
Output is correct |
| 6 |
Correct |
171 ms |
5064 KB |
Output is correct |
