| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 544774 |
2022-04-02T16:42:22 Z |
rainboy |
Tri (CEOI09_tri) |
C |
|
240 ms |
30516 KB |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100000
#define N_ (1 << 17)
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int xx[N], yy[N], n;
long long cross2(int x1, int y1, int x2, int y2) {
return (long long) x1 * y2 - (long long) x2 * y1;
}
long long cross3(int x0, int y0, int x1, int y1, int x2, int y2) {
return cross2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}
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]);
}
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 = cross2(xx[ii[j]], yy[ii[j]], xx[i_], yy[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 ii_[N], cnt;
int merge(int *ii1, int cnt1, int *ii2, int cnt2, int sign) {
int h1, h2;
h1 = h2 = 0, cnt = 0;
while (h1 < cnt1 && h2 < cnt2) {
int c = xx[ii1[h1]] != xx[ii2[h2]] ? xx[ii1[h1]] - xx[ii2[h2]] : yy[ii1[h1]] - yy[ii2[h2]], i;
if (c < 0)
i = ii1[h1++];
else if (c > 0)
i = ii2[h2++];
else
i = ii1[h1], h1++, h2++;
while (cnt >= 2 && cross(ii_[cnt - 2], ii_[cnt - 1], i) * sign >= 0)
cnt--;
ii_[cnt++] = i;
}
while (h1 < cnt1) {
int i = ii1[h1++];
while (cnt >= 2 && cross(ii_[cnt - 2], ii_[cnt - 1], i) * sign >= 0)
cnt--;
ii_[cnt++] = i;
}
while (h2 < cnt2) {
int i = ii2[h2++];
while (cnt >= 2 && cross(ii_[cnt - 2], ii_[cnt - 1], i) * sign >= 0)
cnt--;
ii_[cnt++] = i;
}
return cnt;
}
int ii[N], *iiu[N_ * 2], *iid[N_ * 2], kku[N_ * 2], kkd[N_ * 2], n_;
void build(int n) {
int i;
for (i = 0; i < n; i++)
ii[i] = i;
sort(ii, 0, n);
n_ = 1;
while (n_ < n)
n_ <<= 1;
for (i = 0; i < n_; i++) {
iiu[n_ + i] = (int *) malloc(1 * sizeof *iiu[n_ + i]);
iid[n_ + i] = (int *) malloc(1 * sizeof *iid[n_ + i]);
if (i < n)
iiu[n_ + i][kku[n_ + i]++] = iid[n_ + i][kkd[n_ + i]++] = ii[i];
}
for (i = n_ - 1; i > 0; i--) {
kku[i] = merge(iiu[i << 1 | 0], kku[i << 1 | 0], iiu[i << 1 | 1], kku[i << 1 | 1], 1);
iiu[i] = (int *) malloc(kku[i] * sizeof *iiu[i]);
memcpy(iiu[i], ii_, kku[i] * sizeof *ii_);
kkd[i] = merge(iid[i << 1 | 0], kkd[i << 1 | 0], iid[i << 1 | 1], kkd[i << 1 | 1], -1);
iid[i] = (int *) malloc(kkd[i] * sizeof *iid[i]);
memcpy(iid[i], ii_, kkd[i] * sizeof *ii_);
}
}
int search(int x, int y) {
int lower = -1, upper = n;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (cross2(xx[ii[h]], yy[ii[h]], x, y) < 0)
lower = h;
else
upper = h;
}
return lower;
}
int query_(int i, int x1, int y1, int x2, int y2) {
int lower, upper;
if (x1 < x2) {
lower = -1, upper = kkd[i];
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (cross3(x1, y1, x2, y2, xx[iid[i][h]], yy[iid[i][h]]) < 0)
return 1;
if (h + 1 < kkd[i] && cross2(x2 - x1, y2 - y1, xx[iid[i][h + 1]] - xx[iid[i][h]], yy[iid[i][h + 1]] - yy[iid[i][h]]) < 0)
lower = h;
else
upper = h;
}
} else {
lower = -1, upper = kku[i];
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (cross3(x1, y1, x2, y2, xx[iiu[i][h]], yy[iiu[i][h]]) < 0)
return 1;
if (h + 1 < kku[i] && cross2(x2 - x1, y2 - y1, xx[iiu[i][h + 1]] - xx[iiu[i][h]], yy[iiu[i][h + 1]] - yy[iiu[i][h]]) < 0)
lower = h;
else
upper = h;
}
}
return 0;
}
int query(int l, int r, int x1, int y1, int x2, int y2) {
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1 && query_(l++, x1, y1, x2, y2))
return 1;
if ((r & 1) == 0 && query_(r--, x1, y1, x2, y2))
return 1;
}
return 0;
}
int main() {
int q, i;
scanf("%d%d", &n, &q);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[i], &yy[i]);
build(n);
while (q--) {
int x1, y1, x2, y2, tmp, l, r;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
if (cross2(x1, y1, x2, y2) > 0)
tmp = x1, x1 = x2, x2 = tmp, tmp = y1, y1 = y2, y2 = tmp;
l = search(x1, y1) + 1;
r = search(x2, y2);
printf(l <= r && query(l, r, x1, y1, x2, y2) ? "Y\n" : "N\n");
}
return 0;
}
Compilation message
tri.c: In function 'main':
tri.c:171:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
171 | scanf("%d%d", &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~
tri.c:173:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
173 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tri.c:178:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
178 | scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
2 ms |
468 KB |
Output is correct |
| 3 |
Correct |
39 ms |
7372 KB |
Output is correct |
| 4 |
Correct |
93 ms |
15564 KB |
Output is correct |
| 5 |
Correct |
187 ms |
30516 KB |
Output is correct |
| 6 |
Correct |
209 ms |
27640 KB |
Output is correct |
| 7 |
Correct |
211 ms |
29592 KB |
Output is correct |
| 8 |
Correct |
221 ms |
28788 KB |
Output is correct |
| 9 |
Correct |
237 ms |
29676 KB |
Output is correct |
| 10 |
Correct |
240 ms |
30408 KB |
Output is correct |
