QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#227054#6806. Landlordjzh#WA 273ms3764kbC++202.5kb2023-10-26 20:24:562023-10-26 20:24:57

Judging History

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

  • [2023-10-26 20:24:57]
  • 评测
  • 测评结果:WA
  • 用时:273ms
  • 内存:3764kb
  • [2023-10-26 20:24:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Point {
    ll x, y;
    Point() = default;
    Point(ll x_, ll y_): x(x_), y(y_) {}

    friend Point operator-(Point A, Point B) {return Point(A.x-B.x, A.y-B.y);}

    void input() {
        scanf("%lld%lld", &x, &y);
        x*=2;
        y*=2;
    }
};


bool check_in_rectangle(Point A, Point LD, Point RU) {
    return (
        A.x > LD.x && A.x < RU.x &&
        A.y > LD.y && A.y < RU.y
    );
}

ll mul(Point v1, Point v2) {
    return v1.x*v2.y - v1.y*v2.x;
}

ll sig(ll x) {
    if (x == 0) return 0;
    else if (x > 0) return 1;
    else return -1;
}

bool seg_intersect(Point a1, Point a2, Point a3, Point a4) {
    ll f1, f2;
    f1 = sig(mul(a1-a3, a1-a4)) * sig(mul(a2-a3, a2-a4));
    f2 = sig(mul(a3-a1, a3-a2)) * sig(mul(a4-a1, a4-a2));
    return f1 <= 0 && f2 <= 0;
}

bool check_conn(Point A, Point B, Point LD, Point RU) {
    if (seg_intersect(A, B, Point(LD.x, LD.y), Point(RU.x, LD.y))) return false;
    if (seg_intersect(A, B, Point(RU.x, LD.y), Point(RU.x, RU.y))) return false;
    if (seg_intersect(A, B, Point(RU.x, RU.y), Point(LD.x, RU.y))) return false;
    if (seg_intersect(A, B, Point(LD.x, RU.y), Point(LD.x, LD.y))) return false;
    return true;
}


Point a[100];
bool vis[100];
bool graph[100][100];
int n;


void dfs(int x) {
    vis[x] = 1;
    for (int i=1; i<=n; i++) if (!vis[i] && graph[x][i]) {
        dfs(i);
    }
}

void solve()
{
    vector<Point> p(4);
    Point tmp;
    for (int i=0; i<4; i++) p[i].input();

    
    vector<Point> vec;
    for (int i=0; i<=2; i+=2) {
        Point &A = p[i];
        Point &B = p[i+1];
        vec.emplace_back(A.x, A.y);
        vec.emplace_back(A.x, B.y);
        vec.emplace_back(B.x, A.y);
        vec.emplace_back(B.x, B.y);
    }
    n = 0;
    for (auto A: vec) {
        for (int dx=-1; dx<=1; dx+=2)
            for (int dy=-1; dy<=1; dy+=2) {
                tmp = Point(A.x+dx, A.y+dy);
                a[++n] = tmp;
            }
    }


    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) {
        vis[i] = 0;
        graph[i][j] = (
            check_conn(a[i], a[j], p[0], p[1]) &&
            check_conn(a[i], a[j], p[2], p[3])
        );
    }

    int ans = 0;
    for (int i=1; i<=n; i++) if (!vis[i]) {
        ans++;
        dfs(i);
    }


    printf("%d\n", ans);
}



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

详细

Test #1:

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

input:

3
0 0 1 1
2 2 3 4
1 0 3 2
0 1 2 3
0 0 1 1
0 0 1 1

output:

3
4
2

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 273ms
memory: 3764kb

input:

10000
399413444 601729739 838979329 605646850
176742602 192902430 399413444 601729739
19226489 2915752 27806715 977516728
4075670 1872865 19226489 925008461
45547871 393001695 58201503 713825285
18241876 197851829 45547871 713825285
237513514 504913958 868997719 543598899
134432693 110279295 2375135...

output:

3
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
3
3
4
3
3
4
3
3
4
3
3
4
4
3
3
5
3
3
4
3
3
5
4
3
5
4
3
3
5
3
3
4
4
5
3
3
4
3
4
3
3
3
3
3
4
3
4
3
2
3
3
4
3
3
4
3
3
4
3
3
4
3
3
4
4
3
3
5
3
3
4
4
5
3
3
4
3
4
3
3
3
3
3
4
4
4
4
4
4
4
4
3
3
4
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
4
5
5
3
4
5
...

result:

wrong answer 51st lines differ - expected: '6', found: '5'