QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21985 | #2838. 2D Geometry | gogo | WA | 26ms | 3660kb | C++20 | 1.7kb | 2022-03-08 20:07:13 | 2022-05-08 04:22:58 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++)
#define per(i, r, l) for(int i = (r); i >= (l); i --)
#define trv(i, u, v) for(int i = head[u], v = e[i].to; i; v = e[i = e[i].nxt].to)
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define sz(s) (int)(s.size())
#define lb(s) ((s) & -(s))
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
mt19937_64 hua(time(0));
template<typename T> inline bool chkmx(T &x, T y) {return x < y ? x = y, 1 : 0;}
template<typename T> inline bool chkmn(T &x, T y) {return y < x ? x = y, 1 : 0;}
template<int T> using A = array<int, T>;
inline int read() {
int x = 0, f = 1; char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = 0;
for(; isdigit(c); c = getchar()) x = x * 10 + c - '0';
return f ? x : -x;
}
const int maxn = 2e5;
struct Point {
ll x, y;
friend Point operator - (Point x, Point y) {return {x.x - y.x, x.y - y.y};}
}a[maxn + 5];
int n;
ll cross(Point x, Point y) {
return x.x * y.y - x.y * y.x;
}
int chk() {
random_shuffle(a + 1, a + n + 1);
Point x = a[1], y = a[2];
int cur = 2;
rep(i, 3, n) {
if(cross(x - y, a[i] - y) == 0) cur ++;
else {
cur -= 2;
if(cur < 0) {
x = a[i];
swap(x, y);
cur = 2;
}
}
}
int cnt = 0;
rep(i, 1, n) {
cnt += cross(x - y, a[i] - y) == 0;
}
return max(n % 3, cnt - 2 * (n - cnt));
}
void solve() {
rep(i, 1, n) a[i].x = read(), a[i].y = read();
int ans = 0;
rep(i, 1, 1) {
chkmx(ans, chk());
}
cout << ans << '\n';
}
int main() {
// freopen("in.txt", "r", stdin);
while(cin >> n){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3572kb
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: 3ms
memory: 3604kb
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: 0ms
memory: 3656kb
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: 3ms
memory: 3580kb
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: 4ms
memory: 3660kb
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
Wrong Answer
time: 26ms
memory: 3660kb
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 ...
output:
2 1 0 1 2 2 2 1 2 1 2 4 1 1 2 1 12 1 0 4 2 1 1 6 2 1 0 0 2 2 2 3 1 2 0 2 1 0 13 1 0 1 4 2 1 2 2 8 1 0 1 0 0 0 2 3 1 9 0 2 0 2 20 7 2 8 1 0 8 0 3 7 0 8 14 1 0 2 2 3 0 0 1 1 15 1 1 1 0 2 2 2 4 1 1 1 1 1 0 2 2 11 2 0 0 2 1 8 2 5 0 2 1 0 0 1 8 2 1 0 0 1 1 0 1 9 1 2 7 1 4 7 0 0 1 0 0 0 2 2 2 18 1 2 0 0 0...
result:
wrong answer 4513th lines differ - expected: '3', found: '0'