QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#354126#7693. Convex Hull ExtensionPetroTarnavskyiTL 0ms0kbC++201.6kb2024-03-14 22:05:022024-03-14 22:05:02

Judging History

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

  • [2024-03-14 22:05:02]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-03-14 22:05:02]
  • 提交

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) const
	{
		return (LL)p.x * q.y - (LL)p.y * q.x;
	}
};

LL divFloor(LL p, LL q)
{
	LL res = p / q;
	while (res * q > p)
		res--;
	while ((res + 1) * q <= p)
		res++;
	return res;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<Pt> v(n);
	for (Pt& p : v)
		cin >> p.x >> p.y;
	const int L = -2e6, R = 2e6;
	LL ans = 0;
	bool inf = false;
	FOR(i, 0, n)
	{
		vector<pair<Pt, Pt>> vec = {{v[i], v[(i + 1) % n]}, {v[(i + 2) % n], v[(i + 1) % n]}, {v[(i + 2) % n], v[(i + 3) % n]}};
		LL mxY = L, mnY = R;
		FOR(x, L, R)
		{
			for (auto l : vec)
			{
				if (l.F.x < l.S.x)
				{
					mnY = max(mnY, divFloor((LL)(l.S.y - l.F.y) * (x - l.F.x), l.S.x - l.F.x) + 1 + l.F.y);
				}
				else
				{
					mxY = min(mxY, divFloor((LL)(l.S.y - l.F.y) * (x - l.F.x) - 1, l.S.x - l.F.x) + l.F.y);
				}
			}
			LL s = max(0LL, mxY - mnY + 1);
			inf |= (x == L || x == R - 1) && s > 0;
			ans += s;
		}
	}
	if (inf)
		cout << "infinitely many\n";
	else
		cout << ans << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

5
0 2
-2 0
-1 -3
1 -3
2 1

output:


result: