QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#233948 | #2838. 2D Geometry | SGColin# | WA | 1ms | 3656kb | C++17 | 1.4kb | 2023-11-01 10:28:35 | 2023-11-01 10:28:36 |
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 rep(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;
++f[mt(dy, -dx, dy * x[i] - dx * y[i])];
};
if (n <= 30) {
rep(i, 1, n) rep(j, i + 1, n) calc(i, j);
} else {
int tim = n * 10;
rep(tt, 1, tim) {
int i = rand() % (n - 1) + 1;
int j = i + rand() % (n - i) + 1;
calc(i, j);
}
}
tlll ret = f.begin() -> first;
for (auto [w, cnt] : f) if (cnt > f[ret]) ret = w;
auto [a, b, c] = ret;
int cnt = 0;
rep(i, 1, n) if (a * x[i] + b * y[i] == c) ++cnt;
int rem = n - cnt;
printf("%d\n", rem * 2 >= cnt ? 0 : cnt - rem * 2);
fflush(stdout);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3656kb
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: 1ms
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:
1 2 3 0 1 0 4 0 2 0 0 5 0 0 0 0 0 0 0 3 0 6
result:
wrong answer 6th lines differ - expected: '1', found: '0'