QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#62243#2838. 2D Geometryxuancx#WA 1ms3000kbC++203.9kb2022-11-17 17:49:302022-11-17 17:49:33

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 17:49:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3000kb
  • [2022-11-17 17:49:30]
  • 提交

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 = 3e4 + 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;
        }

        long double xave = 0, yave = 0, up = 0, down = 0;
        for (int i = 0; i < n; i++)
        {
            xave += p[i].first;
            yave += p[i].second;
        }
        xave /= n;
        yave /= n;
        for (int i = 0; i < n; i++)
        {
            up += (p[i].first - xave) * (p[i].second - yave);
            down += (p[i].first - xave) * (p[i].first - xave);
        }
        long double k = up / down;
        long double b = yave - k * xave;
        int ppp = 0;
        for (int i = 1; i <= n; ++i)
        {
            ppp += fabs(k * p[i].first + b - p[i].second) < 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
Wrong Answer
time: 1ms
memory: 3000kb

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:

0
0
0

result:

wrong answer 1st lines differ - expected: '3', found: '0'