QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#233981 | #2838. 2D Geometry | SGColin# | WA | 0ms | 3708kb | C++17 | 1.7kb | 2023-11-01 11:53:38 | 2023-11-01 11:53:38 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<ll, ll, ll> tlll;
inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '0');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define N 200007
ll n, x[N], y[N];
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
map<tlll, int> f;
int main() {
while (scanf("%lld", &n) != EOF) {
f.clear();
rep(i, 1, n) x[i] = rd(), y[i] = rd();
auto calc = [&](int i, int j) {
ll dx = x[i] - x[j];
ll dy = y[i] - y[j];
ll g = gcd(abs(dx), abs(dy));
dx /= g; dy /= g;
if (dx < 0) dx = -dx, dy = -dy;
else if (dx == 0) dy = abs(dy);
++f[mt(dy, -dx, dy * x[i] - dx * y[i])];
};
if (n <= 100) {
rep(i, 1, n) rep(j, i + 1, n) calc(i, j);
} else {
int tim = n * 100;
rep(tt, 1, tim) {
int i = rand() % (n - 1) + 1;
int j = i + rand() % (n - i) + 1;
calc(i, j);
}
}
vector<pair<int, tlll> > s;
for (auto [w, cnt] : f) s.eb(cnt, w);
sort(all(s)); reverse(all(s));
bool fl = false;
per(i, min(10, (int)s.size() - 1), 0) {
auto [a, b, c] = s[i].second;
int cnt = 0;
rep(i, 1, n) if (a * x[i] + b * y[i] == c) ++cnt;
int rem = n - cnt;
if (rem * 2 < cnt) {
//printf("%lld %lld %lld\n", a, b, c);
fl = true; printf("%d\n", cnt - rem * 2);
}
}
if (!fl) puts("0");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3708kb
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: 0ms
memory: 3636kb
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:
0 2 3 0 1 0 4 0 2 0 0 5 0 0 0 0 0 0 0 3 0 6
result:
wrong answer 1st lines differ - expected: '1', found: '0'