QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#674232#5276. K-Shaped FiguresIllusionaryDominanceWA 3ms4120kbC++204.8kb2024-10-25 14:39:462024-10-25 14:39:46

Judging History

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

  • [2024-10-25 14:39:46]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:4120kb
  • [2024-10-25 14:39:46]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using pii = pair <int, int>;

inline int untitled(const pii &a) {
    if (a.first < 0) {
        // x < 0
        return a.second < 0 ? 3 : 2;
    }else {
        return a.second < 0 ? 4 : 1;
    }
}

inline bool cmp(const pii &a, const pii &b) {
    int a_ = untitled(a), b_ = untitled(b);
    if (a_ != b_) return a_ < b_;
    // dya / dxa < dyb / dxb
    return 1ll * a.second * b.first < 1ll * a.first * b.second;
}

inline bool cmp2(const pii &a, const pii &b) {
    int a_ = untitled(a), b_ = untitled(b);
    if (a_ != b_) return 0;
    // dya / dxa < dyb / dxb
    return 1ll * a.second * b.first == 1ll * a.first * b.second;
}

const int MAX_N = 1000 + 5;

int N;
struct Segment{
    int x1, y1, x2, y2;
    Segment (int x1_ = 0, int y1_ = 0, int x2_ = 0, int y2_ = 0) : x1(x1_), y1(y1_), x2(x2_), y2(y2_) {}
    inline bool operator < (const Segment &comp) const {
        return cmp(pair(x2 - x1, y2 - y1), pair(comp.x2 - comp.x1, comp.y2 - comp.y1));
        // return atan2(y2 - y1, x2 - x1) < atan2(comp.y2 - comp.y1, comp.x2 - comp.x1);
    }
}seg[MAX_N];
pii node[MAX_N << 1];

inline bool check(const Segment &seg, int x0, int y0) {
    int dx1 = x0 - seg.x1, dy1 = x0 - seg.y1;
    int dx2 = seg.x2 - x0, dy2 = seg.y2 - y0;
    // dy1 / dx1 = dy2 / dx2
    return 1ll * dy1 * dx2 == 1ll * dx1 * dy2 && min(seg.x1, seg.x2) <= x0 && x0 <= max(seg.x1, seg.x2);
}

void solve() {
    cin >> N;
    for (int i = 1; i <= N; i ++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        node[i] = pair(x1, y1);
        node[i + N] = pair(x2, y2);
        seg[i] = Segment(x1, y1, x2, y2);
    }
    int ans = 0;
    sort(node + 1, node + (N << 1) + 1);
    int M = unique(node + 1, node + (N << 1) + 1) - node - 1;
    for (int i = 1; i <= M; i ++) {
        auto [x0, y0] = node[i];
        vector <Segment> seg1;
        vector <pii> seg2;
        for (int j = 1; j <= N; j ++) {
            if (seg[j].x1 == x0 && seg[j].y1 == y0) {
                seg2.emplace_back(seg[j].x2 - seg[j].x1, seg[j].y2 - seg[j].y1);
            }else if (seg[j].x2 == x0 && seg[j].y2 == y0) {
                seg2.emplace_back(seg[j].x1 - seg[j].x2, seg[j].y1 - seg[j].y2);
            }else if (check(seg[j], x0, y0)) {
                seg1.push_back(seg[j]);
            }
        }
        if (!(seg1.empty() || seg2.empty())) {
            sort(seg1.begin(), seg1.end());
            sort(seg2.begin(), seg2.end(), cmp);
            auto ed = unique(seg2.begin(), seg2.end());
            int n = ed - seg2.begin();
            if(n <= 1) continue;
            int i1 = 0, j1 = n - 1, i2 = n - 1, j2 = 0;
            fprintf(stderr, "n = %d\n", n);
            for (int i = 0; i < n; i ++) fprintf(stderr, "i = %d, dx = %d, dy = %d\n", i, seg2[i].first, seg2[i].second);
            for (int k = 0; k < (int)seg1.size(); k ++) {
                pii dir0 = pair(seg1[k].x2 - seg1[k].x1, seg1[k].y2 - seg1[k].y1);
                pii dir1 = pair(seg1[k].x1 - seg1[k].x2, seg1[k].y1 - seg1[k].y2);
                
                fprintf(stderr, "k = %d, dir0 = (%d, %d), dir1 = (%d, %d)\n", k, dir0.first, dir0.second, dir1.first, dir1.second);
                
                // i1 < dir0, j1 > dir1
                if (cmp(dir0, seg2[i1])) i1 = 0;
                if (cmp(seg2[j1], dir1)) j1 = n - 1;
                while (i1 < n && cmp(seg2[i1], dir0)) i1 ++;
                i1 --; if (i1 < 0) i1 = n - 1;
                while (j1 >= 0 && cmp(dir1, seg2[j1])) j1 --;
                j1 ++; if (j1 == n) j1 = 0;
                
                // i2 > dir0, j2 < dir1
                // if (cmp(seg2[i2], dir0)) i2 = n - 1;
                // if (cmp(dir1, seg2[j2])) j2 = 0;
                // while (i2 >= 0 && cmp(dir0, seg2[i2])) i2 --;
                // i2 ++; if (i2 == n) i2 = 0;
                // while (j2 < n && cmp(seg2[j2], dir1)) j2 ++;
                // j2 --; if (j2 < 0) j2 = n - 1;
                
                int cnt0 = (j1 <= i1 ? i1 - j1 + 1 : n - (j1 - i1 - 1)), cnt1 = n - cnt0;
                i2 = i1 + 1; if (i2 == n) i2 = 0;
                j2 = j1 - 1; if (j2 < 0) j2 = n - 1;
                if (cmp2(seg2[i2], dir0)) cnt1 --;
                if (j2 != i2 && cmp2(seg2[j2], dir1)) cnt1 --;
                
                fprintf(stderr, "cnt0 = %d, cnt1 = %d, i1 = %d, j1 = %d, i2 = %d, j2 = %d\n", cnt0, cnt1, i1, j1, i2, j2);
                
                ans += (cnt0 * (cnt0 - 1) + cnt1 * (cnt1 - 1)) / 2;
            }
        }
    }
    cout << ans << '\n';
    // exit(0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int T; cin >> T;
    while (T --) solve();
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3748kb

input:

2
5
0 0 0 10
0 5 3 10
0 5 3 0
0 5 7 4
0 5 6 2
8
0 0 10 10
3 4 4 4
4 4 4 5
3 4 4 4
7 7 7 8
7 7 8 7
5 5 4 6
5 5 3 7

output:

6
2

result:

ok 2 number(s): "6 2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 4120kb

input:

10
3
-1 -1 0 -1
-1 -1 0 -1
-1 -1 1 1
3
1 -1 0 0
0 -1 1 1
0 1 1 -1
3
0 -1 1 1
-1 1 1 -1
1 1 -1 0
3
-1 0 0 1
-1 1 0 1
-1 1 -1 0
3
-1 1 1 1
1 0 0 -1
1 -1 -1 0
3
0 -1 0 0
1 -1 0 0
-1 -1 1 1
3
1 0 1 1
1 -1 1 0
0 -1 -1 0
3
1 1 0 -1
-1 0 0 1
0 1 -1 0
3
1 0 0 -1
1 0 1 -1
1 0 0 0
3
-1 -1 -1 0
1 -1 1 0
1 0 0 -1

output:

0
0
0
0
0
1
0
0
0
0

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

10
3
-3 2 -2 -1
3 -2 3 -4
3 4 2 5
3
0 -1 5 2
-4 -2 -1 5
1 4 5 -4
3
-3 5 -5 -5
-5 -4 -1 -3
-1 -5 -5 -1
3
-3 3 3 5
1 5 -4 5
2 -5 4 -5
3
4 2 -4 1
1 -5 1 4
-3 5 0 -3
3
3 -3 4 -2
-4 0 -5 -2
-5 2 -1 -4
3
4 -3 2 5
-3 -5 1 -4
5 2 0 5
3
-5 4 -4 -2
-5 -2 -5 2
2 4 -2 -5
3
2 -2 -4 0
2 4 0 -5
-4 -3 0 -4
3
2 5 1 ...

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

10
3
17 -61 16 46
-77 4 48 29
-83 -85 64 -98
3
8 87 72 94
-48 72 -53 -78
-55 95 76 6
3
58 -2 -20 -59
57 20 -50 -7
24 -51 -87 38
3
-20 43 38 73
-13 -14 28 -67
-26 -100 -45 55
3
18 -23 85 -71
-31 -30 7 -54
68 -33 -78 -21
3
-71 36 -11 -53
-43 -2 27 -31
-24 -30 10 71
3
-4 -26 74 -83
12 -86 -73 -58
50 -8...

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

10
3
-747205 986354 -977580 581513
-666338 455489 -636199 888600
-729203 319266 -350608 -89261
3
-449879 -106071 923151 488259
-503807 220920 -120026 346138
110986 442433 -18303 -189764
3
-620049 -67194 -918363 -449594
848473 640562 267788 -183468
846086 972796 -635121 98853
3
-762212 49768 -558584 ...

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #6:

score: -100
Wrong Answer
time: 3ms
memory: 4052kb

input:

3333
3
1 0 0 0
1 1 -1 0
1 0 0 0
3
-1 0 1 0
1 0 1 -1
1 0 0 -1
3
-1 -1 0 -1
-1 -1 0 0
1 -1 1 1
3
1 1 0 -1
-1 0 0 0
0 0 1 0
3
-1 1 -1 0
-1 0 0 1
-1 -1 1 -1
3
0 -1 1 0
1 1 -1 -1
0 1 1 0
3
0 0 1 0
0 1 1 1
0 -1 0 0
3
1 1 -1 1
0 -1 -1 1
1 0 -1 0
3
1 1 -1 0
-1 1 1 0
0 0 -1 -1
3
-1 -1 -1 1
0 0 1 -1
-1 -1 1 1...

output:

0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
8
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 5th numbers differ - expected: '0', found: '1'