QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#62291 | #4538. Bowling | qinjianbin | RE | 0ms | 0kb | C++ | 5.3kb | 2022-11-17 21:55:52 | 2022-11-17 21:55:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define db long double
const db EPS = 1e-8;
inline int sgn(db x) { return x < -EPS ? -1 : x > EPS; }
struct Point {
db x, y;
Point(db x = 0, db y = 0) : x(x), y(y) {}
void input() { scanf("%Lf%Lf", &x, &y); }
Point operator+(Point r) { return Point(x + r.x, y + r.y); }
Point operator-(Point r) { return Point(x - r.x, y - r.y); }
db len2() { return x * x + y * y; }
};
db Cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
db Cross(Point a, Point b, Point c) { return Cross(b - a, c - a); }
int minslope(Point *p, int l, int r, Point pt, int w) {
while (l < r) {
int mid = l + r >> 1;
if (sgn(Cross(pt, p[mid], p[mid + 1])) * w >= 0)
r = mid;
else
l = mid + 1;
}
return l;
}
int border(Point *p, int l, int r, db x, int w) {
while (l < r) {
int mid = l + r >> 1;
if (sgn(x - p[mid].x) * w <= 0)
r = mid;
else
l = mid + 1;
}
return l;
}
pair<int, int> pptangertpcon(Point *p, int n, Point pt, int Rx) {
int L, R, Mid;
if (sgn(pt.x - p[0].x) < 0) {
L = minslope(p, 0, Rx, pt, 1), R = minslope(p, Rx, n, pt, -1);
} else if (sgn(pt.x - p[Rx].x) > 0) {
L = minslope(p, 0, Rx, pt, -1), R = minslope(p, Rx, n, pt, 1);
} else if (Cross(pt, p[0], p[Rx]) > 0) {
Mid = border(p, Rx, n, pt.x, -1);
L = Mid > Rx ? minslope(p, Rx, Mid - 1, pt, -1) : Mid;
R = minslope(p, Mid, n, pt, 1);
} else {
Mid = border(p, 0, Rx, pt.x, 1);
L = Mid > 0 ? minslope(p, 0, Mid - 1, pt, -1) : 0;
R = minslope(p, Mid, Rx, pt, 1);
}
return make_pair(L, R);
}
// bool operator < (Point a, Point b) {
// if (sgn(a.x - b.x) == 0) return a.y < b.y;
// return a.x < b.x;
// }
void change(Point *p, Point *tmp, int n, int &Rx) {
int Mii = 0;
for (int i = 0; i < n; i++) {
if (p[i].x < p[Mii].x) Mii = i;
tmp[i] = p[i];
}
int i;
for (i = 0; Mii < n; Mii++, i++)
p[i] = tmp[Mii];
for (Mii = 0; i < n; Mii, i++)
p[i] = tmp[Mii];
Rx = 0;
for (int i = 0; i < n; i++)
if (p[i].x > p[Rx].x) Rx = i;
}
const int MAXN = 1e5 + 10;
int n, m, q;
Point p[MAXN], tmp[MAXN], pp;
Point base(0, 0);
int quad(Point r) {
int sx = sgn(r.x - base.x), sy = sgn(r.y - base.y);
if (sx > 0 && sy >= 0) return 0;
if (sx <= 0 && sy > 0) return 1;
if (sx < 0 && sy <= 0) return 2;
return 3;
}
bool cmp(Point a, Point b) { // a < b
int qa = quad(a), qb = quad(b);
if (qa != qb) return qa < qb;
int c = sgn(Cross(base, a, b));
if (c == 0) return (a - base).len2() > (b - base).len2();
return c > 0;
}
bool cmp2(Point a, Point b) {
int qa = quad(a), qb = quad(b);
if (qa != qb) return qa < qb;
return sgn(Cross(base, a, b));
}
struct Seg {
Point p;
int cnt = 0;
Seg(Point p = Point(0, 0), int cnt = 0) : p(p), cnt(cnt) {}
bool operator< (const Seg & a) const {
return cmp(p, a.p);
}
} seg[MAXN << 2];
int sidx = 0;
struct Que {
Point dir;
int id;
bool operator< (const Que& a) const {
return cmp(dir, a.dir);
}
}que[MAXN];
int ans[MAXN];
void solve() {
sidx = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
p[i].input();
int Rx;
change(p, tmp, n, Rx);
// for (int i = 0; i < n; i++)
// printf("%.1Lf %.1Lf\n", p[i].x, p[i].y);
// printf("%d\n", Rx);
scanf("%d", &m);
for (int i = 0; i < m; i++) {
pp.input();
pair<int, int> tmp = pptangertpcon(p, n, pp, Rx);
// printf("%d %d ", tmp.first, tmp.second);
Point tmpp[2] = {Point(pp - p[tmp.first]), Point(pp - p[tmp.second])};
if (sgn(Cross(tmpp[0], tmpp[1])) < 0) swap(tmpp[0], tmpp[1]);
// printf("%.1Lf %.1Lf %.1Lf %.1Lf\n", tmpp[0].x, tmpp[0].y, tmpp[1].x, tmpp[1].y);
if (tmpp[0].y < 0 && tmpp[1].y >= 0) {
seg[sidx++] = Seg(tmpp[0], 1);
seg[sidx++] = Seg(Point(1e18, -1), -1);
seg[sidx++] = Seg(Point(1, 0), 1);
seg[sidx++] = Seg(tmpp[1], -1);
}
else {
seg[sidx++] = Seg(tmpp[0], 1);
seg[sidx++] = Seg(tmpp[1], -1);
}
}
sort(seg, seg + sidx);
scanf("%d", &q);
for (int i = 0; i < q; i++)
que[i].dir.input(), que[i].id = i;
sort(que, que + q);
// for (int i = 0; i < q; i++)
// printf("%.1Lf %.1Lf\n", que[i].dir.x, que[i].dir.y);
int cnt = 0, ssidx = 0;
for (int i = 0; i < q; i++) {
while (ssidx < sidx) {
if (cmp2(que[i].dir, seg[ssidx].p)) break;
cnt += seg[ssidx].cnt;
ssidx++;
}
// printf("asd %d\n", ssidx);
ans[que[i].id] = cnt;
}
for (int i = 0; i < q; i++)
printf("%d\n", ans[i]);
// for (int i = 0; i < sidx; i++)
// printf("%.1Lf %.1Lf %d\n", seg[i].p.x, seg[i].p.y, seg[i].cnt);
}
int main() {
freopen("D:\\Cpp\\1.in", "r", stdin);
freopen("D:\\Cpp\\1.out", "w", stdout);
int T;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 0
Dangerous Syscalls
input:
56 4 0 0 2 0 2 2 0 2 5 1 4 3 1 4 2 5 1 3 3 3 0 1 1 0 1 1 3 -9 -5 -1 -2 -3 0 100 7 -49 -69 81 20 77 -3 47 2 45 76 82 65 -70 85 3 82 62 23 -32 83 -66 58 -58 52 -90 4 -33 5 -97 -8 62 89 -64 31 -88 19 87 -62 -34 7 55 12 2 16 77 93 -7 13 15 -21 62 41 72 55 13 -70 45 -5 49 51 93 73 -21 3 22 -49 22 -83 -80...