QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369649#2827. AutobiographyPetroTarnavskyi#WA 1ms3612kbC++201.2kb2024-03-28 15:51:382024-03-28 15:51:38

Judging History

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

  • [2024-03-28 15:51:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3612kb
  • [2024-03-28 15:51:38]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

struct Pt
{
	int x, y;
	Pt operator-(const Pt& p) const
	{
		return {x - p.x, y - p.y};
	}
};

LL cross(const Pt& p, const Pt& q)
{
	return (LL)p.x * q.y - (LL)p.y * q.x;
}

mt19937 rng;

int n;

void solve()
{
	vector<Pt> v(n);
	for (Pt& p : v)
		cin >> p.x >> p.y;
	const int MAGIC = 74;
	int m = 1;
	FOR(i, 0, MAGIC)
	{
		int i1 = rng() % n, i2 = rng() % n;
		if (i1 == i2)
			continue;
		Pt p1 = v[i1], p2 = v[i2];
		int cur = 0;
		for (const Pt& p : v)
		{
			if (cross(p - p1, p - p2) == 0)
			{
				cur++;
			}
		}
		assert(cur >= 2);
		m = max(m, cur);
	}
	int ans = n - 3 * (n - m);
	if (ans < 0)
	{
		ans = n % 3;
	}
	cout << ans << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	while (cin >> n)
		solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3612kb

input:

5 4
bbobo
1 3
2 3
3 4
4 5
4 6
bobo
1 2
1 3
1 4
2 3
2 4
3 4
4 0
bobo

output:

5

result:

wrong answer 1st lines differ - expected: '2', found: '5'