QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#198404 | #2838. 2D Geometry | vanthoci# | TL | 0ms | 3788kb | C++17 | 1.4kb | 2023-10-03 13:41:11 | 2023-10-03 13:41:12 |
Judging History
answer
#include<bits/stdc++.h>
// #define int long long
using namespace std ;
using i64 = long long;
random_device SEED;
mt19937 RAND(SEED());
struct solve{
int n;
struct P{
int x, y;
P() { x = y = 0; }
P(int xx, int yy) { x = xx , y = yy; }
void getIt(){
cin >> x >> y;
}
friend i64 operator ^(P a, P b){
return 1LL * a.x * b.y - 1LL * b.x * a.y;
}
friend P operator -(P a, P b){
return P(a.x - b.x, a.y - b.y);
}
};
vector<P> v;
// solve() {cout << "called\n";}
solve(int _n){
n = _n;
v.assign(n, P());
for (auto& x : v) x.getIt();
int omega = 100;
int max_coline = 0;
while (omega --){
int now_coline = 0;
int x = RAND() % n, y = RAND() % n;
while (y == x) y = RAND() % n;
for(auto vz : v){
if(((vz - v[x]) ^ (vz - v[y])) == 0) now_coline++;
}
max_coline = max(max_coline, now_coline);
}
if (max_coline <= (n - max_coline) * 2) {
cout << n % 3 << '\n';
}else {
cout << max_coline - (n - max_coline) * 2 << '\n';
}
}
};
signed main(){
ios::sync_with_stdio(0);cin.tie(0) ;
int n;
while(cin >> n){
auto x = solve(n) ;
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3788kb
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 ...