QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21983#2838. 2D GeometrygogoWA 3ms3452kbC++201.7kb2022-03-08 20:06:302022-05-08 04:22:49

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 04:22:49]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3452kb
  • [2022-03-08 20:06:30]
  • 提交

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: ''