QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#62196#2832. Graph Theoryxuancx#TL 0ms0kbC++204.0kb2022-11-17 16:58:212022-11-17 16:58:26

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 16:58:26]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-11-17 16:58:21]
  • 提交

answer

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <random>
#include <tuple>
using namespace std;

#define int long long

constexpr int maxn = 2e5 + 1;
constexpr int times = 4e5 + 1;
constexpr double eps = 1e-6;

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

struct Rational
{
    Rational() : x(0), y(1) {}
    Rational(int _x, int _y) : x(_x), y(_y)
    {
        auto g = __gcd(x, y);
        x /= g;
        y /= g;
    }
    void set(int _x, int _y)
    {
        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;
        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;
        }
        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;
        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)y / x; }
    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;
        l.norm.k.set(b.second - a.second, b.first - a.first);
        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 = 0;
        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 < times)
        {
            auto a = dist(rd);
            auto b = dist(rd);
            l = construct(p[a], p[b]);
            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;
            }
        }
        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: 0
Time Limit Exceeded

input:

3 2
1 2
2 3
3 2
1 1
2 2
3 3
1 2
2 3
3 1

output:


result: