QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#62273#2838. 2D Geometryxuancx#WA 166ms3724kbC++205.1kb2022-11-17 18:53:512022-11-17 18:53:53

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 18:53:53]
  • 评测
  • 测评结果:WA
  • 用时:166ms
  • 内存:3724kb
  • [2022-11-17 18:53:51]
  • 提交

answer

#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <map>
#include <random>
#include <tuple>
using namespace std;

#define int long long

constexpr int maxn = 2e5 + 100;
constexpr int times = 3e4 + 1;
constexpr double eps = 1e-8;

int n;
pair<int, int> p[maxn];

struct Rational
{
    Rational() : x(0), y(1) {}
    Rational(int _x, int _y) : x(_x), y(_y)
    {
        if (!x)
            return;
        auto g = __gcd(x, y);
        x /= g;
        y /= g;
    }
    void set(int _x, int _y)
    {
        x = _x;
        y = _y;
        if (!x)
            return;
        auto g = __gcd(_x, _y);
        x = _x / g;
        y = _y / g;
    }
    Rational operator+(const Rational &rhs) const
    {
        Rational r = *this;
        if (rhs.y == r.y)
        {
            r.x += rhs.x;
            return r;
        }
        auto base = r.y * rhs.y;
        r.x *= rhs.y;
        r.x += rhs.x * r.y;
        if (!r.x)
            return r;
        auto g = __gcd(base, r.x);
        r.x /= g;
        r.y = base / g;
        return r;
    }
    Rational operator-(const Rational &rhs) const
    {
        Rational r = *this;
        if (rhs.y == r.y)
        {
            r.x -= rhs.x;
            return r;
        }
        if (!r.x)
            return r;
        auto base = r.y * rhs.y;
        r.x *= rhs.y;
        r.x -= rhs.x * r.y;
        auto g = __gcd(base, r.x);
        r.x /= g;
        r.y = base / g;
        return r;
    }
    Rational operator*(int k)
    {
        auto r = *this;
        r.x *= k;
        if (!r.x)
            return r;
        auto g = __gcd(r.x, r.y);
        r.x /= g;
        r.y /= g;
        return r;
    }
    bool operator<(const Rational &rhs) const
    {
        return y == rhs.y ? x < rhs.x : y < rhs.y;
    }
    bool operator==(const Rational &rhs) const
    {
        return x == rhs.x && y == rhs.y;
    }
    int getx() { return x; }
    int gety() { return y; }
    double approx() const { return (double)x / y; }
    int x, y;
};

struct normal
{
    Rational k, b;
};

struct perp
{
    int x = 0;
};

struct Line
{
    bool isNormal;
    normal norm;
    perp p;
    bool operator<(const Line &rhs) const
    {
        if (!isNormal)
            return rhs.isNormal ? true : p.x < rhs.p.x;
        else if (!rhs.isNormal)
        {
            return false;
        }
        else
        {
            if (norm.k == rhs.norm.k)
            {
                return norm.b < rhs.norm.b;
            }
            else
            {
                return norm.k < rhs.norm.k;
            }
        }
    }
};

Line construct(pair<int, int> a, pair<int, int> b)
{
    Line l;
    if (a.first == b.first)
    {
        l.isNormal = false;
        l.p.x = a.first;
    }
    else
    {
        l.isNormal = true;
        if (b.second == a.second)
        {
            l.norm.k.x = 0;
            l.norm.k.y = 1;
            l.norm.b.x = a.second;
            l.norm.b.y = 1;
            return l;
        }
        else
        {
            l.norm.k.set(b.second - a.second, b.first - a.first);
            // printf("DEBUG:: k = %lf\n", l.norm.k.approx());
            l.norm.b = Rational(a.second, 1) - l.norm.k * a.first;
        }
    }
    return l;
}

map<Line, int> mp;

signed main(void)
{
    random_device rd;
    while (scanf("%lld", &n) != EOF)
    {
        mp.clear();
        int cnt = 1;
        while (cnt <= n)
        {
            scanf("%lld%lld", &p[cnt].first, &p[cnt].second);
            ++cnt;
        }
        if (n == 1)
        {
            printf("1\n");
            continue;
        }
        uniform_int_distribution<int> dist(1, n);
        cnt = 0;
        int mx = 0, other = 0;
        Line l, idx;
        while (++cnt < 10)
        {
            int a = dist(rd);
            int b = dist(rd);
            while (a == b)
                b = dist(rd);
            l = construct(p[a], p[b]);
            // printf("DEBUG:: Type: %lld\n", l.isNormal);
            // if (l.isNormal)
            // {
            //     // printf("DEBUG:: %lf %lf\n", l.norm.k.approx(), l.norm.b.approx());
            // }
            // else
            // {
            //     // printf("DEBUG:: %lld\n", l.p.x);
            // }
            if (++mp[l] > mx)
            {
                mx = mp[l];
                idx = l;
            }
        }
        int ppp = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (!idx.isNormal)
            {
                ppp += p[i].first == idx.p.x;
            }
            else
            {
                ppp += fabs((Rational(p[i].second, 1) - idx.norm.k * p[i].first - idx.norm.b).approx()) < eps;
            }
        }
        // printf("??:%lld\n", ppp);
        if (ppp > 2 * (n - ppp))
        {
            printf("%lld\n", ppp - 2 * (n - ppp));
        }
        else
        {
            printf("%lld\n", n % 3);
        }
    }
}

详细

Test #1:

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

input:

3
0 0
0 1
0 2
3
0 0
0 1
1 0
6
0 0
0 1
0 2
0 3
1 1
1 2

output:

3
0
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 3672kb

input:

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

output:

1
2
3
0
1
1
4
2
2
2
2
5
0
0
0
0
0
0
0
3
0
6

result:

ok 22 lines

Test #3:

score: 0
Accepted
time: 2ms
memory: 3520kb

input:

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

output:

1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1

result:

ok 21 lines

Test #4:

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

input:

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

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2

result:

ok 57 lines

Test #5:

score: 0
Accepted
time: 3ms
memory: 3724kb

input:

9
14 16
8 14
18 19
0 10
5 9
0 5
1 2
12 9
15 11
9
16 12
3 9
10 14
17 14
6 10
2 19
17 17
0 13
7 2
9
17 1
14 13
5 14
9 2
13 0
1 18
17 13
11 3
5 13
9
13 0
13 3
5 4
6 14
3 5
17 14
5 17
19 17
5 6
9
3 18
18 9
14 14
6 4
17 10
16 15
8 14
10 14
18 16
9
17 10
19 19
1 16
18 17
9 13
10 15
19 3
6 16
17 16
9
13 2
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 86 lines

Test #6:

score: -100
Wrong Answer
time: 166ms
memory: 3480kb

input:

17
87310293 387438180
71556828 322852519
229718797 511837973
310313906 370688881
259858018 463145945
252802375 462493335
347775953 550587600
68053426 326582700
386313403 373022317
211296869 571386994
138237064 241008526
196230475 364801713
327348063 266915603
238976759 498766159
215667837 559919342
...

output:

2
1
0
1
2
2
2
1
2
1
2
4
1
1
2
1
12
1
0
4
2
1
1
6
2
1
0
0
2
2
2
3
1
2
0
2
1
0
13
1
0
1
4
2
1
2
2
8
1
0
1
0
0
0
2
3
1
9
0
2
0
2
20
7
2
8
1
0
8
0
3
7
0
8
14
1
0
2
2
3
0
0
1
1
15
1
1
1
0
2
2
2
4
1
1
1
1
1
0
2
2
11
2
0
0
2
1
8
2
5
0
2
1
0
0
1
8
2
1
0
0
1
1
0
1
9
1
2
7
1
4
7
0
0
1
0
0
0
2
2
2
18
1
2
0
0
0...

result:

wrong answer 1555th lines differ - expected: '4', found: '1'