QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#677101#7693. Convex Hull Extensionnew_game_plus_players#WA 0ms3728kbC++142.6kb2024-10-26 09:49:172024-10-26 09:49:17

Judging History

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

  • [2024-10-26 09:49:17]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3728kb
  • [2024-10-26 09:49:17]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
struct point {
	double x, y;
	point (double X=0, double Y=0) {x=X; y=Y;}
	point operator + (const point &t) const {return point(x+t.x, y+t.y);}
	point operator - (const point &t) const {return point(x-t.x, y-t.y);}
	point operator * (const double &t) const {return point(x*t, y*t);}
	double det(const point &t) const {return x*t.y - y*t.x;}
	double dot(const point &t) const {return x*t.x + y*t.y;}
	double mx() const {return max(x, y);}
	double mn() const {return min(x, y);}
	void out() {
		cerr<<x<<','<<y<<" ";
	}
}a[55];
const double eps = 1e-9;
bool parallel(point a, point b, point c, point d) {
	return fabs((b-a).det(d-c)) < eps;
}
point LxL(point a, point b, point c, point d) { // a-b x c-d
	double t = (c-a).det(d-a) / (b-a).det(d-c);
	return a + (b-a) * t;
}

int n;
bool in_triangle(point p, point a, point b, point c) {
	if ((b-a).det(p-a) < eps) return false;
	if ((c-b).det(p-b) < eps) return false;
	if ((a-c).det(p-c) < eps) return false;
	return true;
}
void solvex(point a, point b, int x, int &l, int &r) {
	if (fabs(a.x - b.x) < eps) {
		return;
	}
	point p = LxL(a, b, point(x, 0), point(x, 1));
	if (a.x < b.x) {
		l = max(l, (int)ceil(p.y + eps));
	} else {
		r = min(r, (int)floor(p.y - eps));
	}
}
ll solve(point a, point b, point c) {
	double R = -1e0;
	R = max(R, a.x);
	R = max(R, b.x);
	R = max(R, c.x);
	double L = 1e9;
	L = min(L, a.x);
	L = min(L, b.x);
	L = min(L, c.x);
	ll ret = 0;
	// cerr<<"solve:";
	// a.out();
	// b.out();
	// c.out();
	// cerr<<"["<<L<<","<<R<<"]"<<endl;

	for (int i=L-2; i<=R+2; i++) {
		int l = -1e9, r = 1e9;
		solvex(a, b, i, l, r);
		solvex(b, c, i, l, r);
		solvex(c, a, i, l, r);
		// cerr<<"i="<<i<<" "<<l<<","<<r<<endl;
		if (l<=r) {
			if (in_triangle(point(i, l), a, b, c)) {
				ret += r-l+1;
			}
		}
		// for (int j=-100; j<=100; j++) {
		// 	ret += in_triangle(point(i,j), a, b, c);
		// }
	}
	return ret;
}
int main() {
	cin>>n;
	for (int i=1; i<=n; i++) {
		cin>>a[i].x>>a[i].y;
	}
	a[0] = a[n];
	a[n+1] = a[1];
	a[n+2] = a[2];
	ll ans = 0;
	for (int i=1; i<=n; i++) {
		if (parallel(a[i-1], a[i], a[i+1], a[i+2])) {
			puts("infinitely many");
			return 0;
		}
		point p = LxL(a[i-1], a[i], a[i+1], a[i+2]);
		double test = (p - a[i]).det(a[i+1] - a[i]);
		if (test < 0) {
			puts("infinitely many");
			return 0;
		}
		ans += solve(a[i], p, a[i+1]);
	}
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3728kb

input:

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

output:

23

result:

ok single line: '23'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

4
-7 -7
7 -7
7 7
-7 7

output:

infinitely many

result:

ok single line: 'infinitely many'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3728kb

input:

4
-1000 1000
-1000 999
-999 999
-999 1000

output:

infinitely many

result:

wrong answer 1st lines differ - expected: '0', found: 'infinitely many'