QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#62210 | #2838. 2D Geometry | xuancx# | WA | 2ms | 3220kb | C++20 | 4.0kb | 2022-11-17 17:01:39 | 2022-11-17 17:01:40 |
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 = 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;
}
uniform_int_distribution<int> dist(1, n);
cnt = 0;
int mx = 0, other = 0;
Line l, idx;
while (++cnt < 2 * n)
{
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);
}
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3220kb
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
Wrong Answer
time: 2ms
memory: 3152kb
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 2 0 0 0 0 0 0 0 3 0 6
result:
wrong answer 12th lines differ - expected: '5', found: '2'