QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#62256#2838. 2D Geometryxuancx#TL 2ms3536kbC++204.9kb2022-11-17 18:40:362022-11-17 18:40:37

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:40:37]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3536kb
  • [2022-11-17 18:40:36]
  • 提交

answer

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

#define int long long

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

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;
        }
        uniform_int_distribution<int> dist(1, n);
        cnt = 0;
        int mx = 0, other = 0;
        Line l, idx;
        while (++cnt < 200)
        {
            auto a = dist(rd);
            auto b = dist(rd);
            while (a == b)
                b = dist(rd);
            l = construct(p[a], p[b]);
            // printf("DEBUG:: Type: %d\n", l.isNormal);
            if (l.isNormal)
            {
                // printf("DEBUG:: %lf %lf\n", l.norm.k.approx(), l.norm.b.approx());
            }
            else
            {
                // printf("DEBUG:: %d\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);
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3536kb

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: -100
Time Limit Exceeded

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:


result: