QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#62196 | #2832. Graph Theory | xuancx# | TL | 0ms | 0kb | C++20 | 4.0kb | 2022-11-17 16:58:21 | 2022-11-17 16:58:26 |
Judging History
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