QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21983 | #2838. 2D Geometry | gogo | WA | 3ms | 3452kb | C++20 | 1.7kb | 2022-03-08 20:06:30 | 2022-05-08 04:22:49 |
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, 2) {
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: 0
Wrong Answer
time: 3ms
memory: 3452kb
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:
result:
wrong answer 1st lines differ - expected: '3', found: ''