QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#62298#4538. BowlingqinjianbinWA 456ms52512kbC++5.5kb2022-11-17 22:26:522022-11-17 22:26:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-17 22:26:56]
  • 评测
  • 测评结果:WA
  • 用时:456ms
  • 内存:52512kb
  • [2022-11-17 22:26:52]
  • 提交

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;
}
int cmp2(Point a, Point b) {
    int qa = quad(a), qb = quad(b);
    if (qa != qb) return qa < qb ? 1 : -1;
    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 {
        int qa = quad(p), qb = quad(a.p);
        if (qa != qb) return qa < qb;
        int c = sgn(Cross(base, p, a.p));
        if (c == 0) return cnt < a.cnt;
        return c > 0;
    }
} seg[MAXN << 3];
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) {
            int flag = cmp2(que[i].dir, seg[ssidx].p);
            if (flag > 0) break;
            else if (flag == 0 && seg[ssidx].cnt == -1) 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() {
#ifdef TanJI
    freopen("D:\\Cpp\\1.in", "r", stdin);
    freopen("D:\\Cpp\\1.out", "w", stdout);
#endif

    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 456ms
memory: 52512kb

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...

output:

1
3
3
1
4
4
6
1
0
0
4
4
0
6
3
1
3
1
0
0
6
3
1
4
3
5
5
2
0
4
1
1
1
4
3
5
3
0
2
0
2
1
0
2
2
1
2
0
0
2
1
1
1
1
0
3
4
5
4
0
3
4
1
0
2
0
2
1
3
1
1
1
0
5
4
4
6
2
2
3
4
1
0
1
4
3
2
1
5
1
1
1
4
4
1
6
1
4
0
2
2
1
1
3
5
5
2
3
3
5
4
2
2
4
5
4
3
7
7
5
2
2
5
2
5
2
0
5
7
2
0
0
4
3
5
2
3
5
3
2
1
3
2
2
5
4
3
5
2
2
...

result:

wrong answer 7th lines differ - expected: '5', found: '6'