QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#354126 | #7693. Convex Hull Extension | PetroTarnavskyi | TL | 0ms | 0kb | C++20 | 1.6kb | 2024-03-14 22:05:02 | 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