QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#62268 | #2838. 2D Geometry | xuancx# | RE | 11ms | 3724kb | C++20 | 5.1kb | 2022-11-17 18:50:52 | 2022-11-17 18:50:54 |
Judging History
answer
#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <map>
#include <random>
#include <tuple>
using namespace std;
// #define int long long
constexpr int maxn = 2e5 + 100;
constexpr int times = 3e4 + 1;
constexpr double eps = 1e-8;
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("%d", &n) != EOF)
{
mp.clear();
int cnt = 1;
while (cnt <= n)
{
scanf("%d%d", &p[cnt].first, &p[cnt].second);
++cnt;
}
if (n == 1)
{
printf("1\n");
continue;
}
uniform_int_distribution<int> dist(1, n);
cnt = 0;
int mx = 0, other = 0;
Line l, idx;
while (++cnt < 100)
{
long long a = dist(rd);
long long 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("??:%d\n", ppp);
if (ppp > 2 * (n - ppp))
{
printf("%d\n", ppp - 2 * (n - ppp));
}
else
{
printf("%d\n", n % 3);
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 3612kb
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: 0
Accepted
time: 5ms
memory: 3536kb
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 5 0 0 0 0 0 0 0 3 0 6
result:
ok 22 lines
Test #3:
score: 0
Accepted
time: 5ms
memory: 3724kb
input:
7 0 1 0 0 7 7 6 2 6 9 4 4 3 5 7 3 7 3 2 9 1 0 6 1 8 5 0 9 5 7 3 7 2 3 4 5 6 7 7 7 5 8 4 7 7 1 6 5 7 7 2 3 5 0 8 8 8 3 8 7 1 8 3 4 8 8 1 9 7 8 1 7 0 0 7 6 9 2 7 4 5 2 1 4 6 2 3 7 6 7 3 1 1 9 5 7 6 6 5 2 5 1 5 3 7 6 4 1 6 7 3 5 4 2 3 0 0 3 2 7 2 9 4 9 8 9 8 0 1 7 2 6 6 2 7 3 5 4 0 4 1 4 3 0 8 4 7 4 6 ...
output:
1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1
result:
ok 21 lines
Test #4:
score: 0
Accepted
time: 10ms
memory: 3520kb
input:
8 3 2 4 4 3 9 7 9 9 3 9 1 4 2 5 3 8 0 6 0 2 1 6 9 9 5 5 8 4 6 8 0 9 8 1 8 8 1 9 0 1 3 6 4 3 6 4 0 1 6 8 5 3 1 0 0 1 7 1 3 7 8 8 6 4 6 2 8 3 3 7 8 0 8 6 3 0 4 2 3 5 3 5 4 8 6 2 9 7 3 2 6 5 2 2 1 5 4 7 2 5 8 1 1 1 0 1 5 2 8 8 9 8 8 0 0 1 4 8 8 0 3 3 8 2 5 5 3 0 0 0 6 2 8 9 8 3 9 3 5 3 1 6 5 6 2 1 1 8 ...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
result:
ok 57 lines
Test #5:
score: 0
Accepted
time: 11ms
memory: 3720kb
input:
9 14 16 8 14 18 19 0 10 5 9 0 5 1 2 12 9 15 11 9 16 12 3 9 10 14 17 14 6 10 2 19 17 17 0 13 7 2 9 17 1 14 13 5 14 9 2 13 0 1 18 17 13 11 3 5 13 9 13 0 13 3 5 4 6 14 3 5 17 14 5 17 19 17 5 6 9 3 18 18 9 14 14 6 4 17 10 16 15 8 14 10 14 18 16 9 17 10 19 19 1 16 18 17 9 13 10 15 19 3 6 16 17 16 9 13 2 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 86 lines
Test #6:
score: -100
Runtime Error
input:
17 87310293 387438180 71556828 322852519 229718797 511837973 310313906 370688881 259858018 463145945 252802375 462493335 347775953 550587600 68053426 326582700 386313403 373022317 211296869 571386994 138237064 241008526 196230475 364801713 327348063 266915603 238976759 498766159 215667837 559919342 ...