QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#59807 | #2838. 2D Geometry | Scarlett_boy | WA | 2ms | 3724kb | C++14 | 1.9kb | 2022-11-01 15:49:27 | 2022-11-01 15:49:30 |
Judging History
answer
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
char nc() {
static char buf[1000000], *p = buf, *q = buf;
return p == q && (q = (p = buf) + fread(buf, 1, 1000000, stdin), p == q) ? EOF : *p++;
}
inline ll read() {
ll x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int n;
struct Point {
ll x, y;
} s[N];
int vis[N];
int calc(int j) {
int now = 0;
map<pair<ll, ll>, int> mp;
for (int i = 1; i <= n; i++) {
if (i == j) continue;
int X = s[i].x - s[j].x, Y = s[i].y - s[j].y;
if (X < 0) {
X = -X;
Y = -Y;
} else if (X == 0) {
if (Y < 0) Y = -Y;
}
mp[make_pair(X, Y)]++;
}
// printf("j=%d:\n", j);
for (auto to: mp) {
now = max(now, to.second + 1);
// printf(" NOW = %d\n", to.second + 1);
}
return now;
}
void solve() {
srand(time(0));
for (int i = 1; i <= n; i++) vis[i] = 0;
for (int i = 1; i <= n; i++) s[i].x = read(), s[i].y = read();
int T = min(n, 50);
int now = 0;
while (T--) {
int x = rand() % n + 1;
while (vis[x]) x = rand() % n + 1;
vis[x] = 1;
now = max(now, calc(x));
}
int last = n - now;
if (now > last * 2) {
printf("%d\n", now - last * 2);
} else {
printf("%d\n", n % 3);
}
}
signed main() {
// int t = read();
// while (t--)
while (scanf("%d", &n) != EOF)
solve();
return 0;
}
/*
1
1
1
1
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3724kb
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: 3568kb
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 1 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0
result:
wrong answer 7th lines differ - expected: '4', found: '1'