QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#62255 | #2838. 2D Geometry | xuancx# | TL | 2ms | 3524kb | C++20 | 4.9kb | 2022-11-17 18:40:11 | 2022-11-17 18:40:14 |
Judging History
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 < 100 * n)
{
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);
}
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3524kb
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 ...