QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#50345#851. (Almost) Fair Cake-CuttingSGColinAC ✓3ms3792kbC++175.3kb2022-09-25 14:12:212022-09-25 14:12:23

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-25 14:12:23]
  • Judged
  • Verdict: AC
  • Time: 3ms
  • Memory: 3792kb
  • [2022-09-25 14:12:21]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = false;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define fr     first
#define sc     second
#define pb     push_back
#define mp     make_pair
#define pii    pair<int, int>
#define all(x) (x).begin(), (x).end() 

typedef double T;
#define let const auto
#define lett const T
#define letp const P
#define lets const S
#define letl const L
#define letc const C

const T eps = 1e-8;
#define z(x) (abs((x)) <= eps)

struct P {
	T x, y;
	P (T x = 0, T y = 0) : x(x), y(y) {}
	P operator + (letp &p) const {return {x + p.x, y + p.y};}
	P operator - (letp &p) const {return {x - p.x, y - p.y};}
	P operator * (lett &d) const {return {x * d, y * d};}
	P operator / (lett &d) const {return {x / d, y / d};}
	P operator - () const {return {-x, -y};}

	T operator | (letp &p) const {return x * p.x + y * p.y;}
	T operator ^ (letp &p) const {return x * p.y - y * p.x;}

	int ori(letp &p) const {T t = (*this) ^ p; return (t > eps) - (t < -eps);}

	T norm() const {return x * x + y * y;}
} zero;

double abs(letp &p) {return sqrt(p.norm());}
P perp(letp &p) {return {-p.y, p.x};}

struct argcmp {
	bool operator() (letp &a, letp &b) const {
		const auto quad = [](letp &a) {
			if (a.y < -eps) return 1;
			if (a.y > eps) return 4;
			if (a.x < -eps) return 5;
			if (a.x > eps) return 3;
			return 2;
		};
		const int qa = quad(a), qb = quad(b);
		if (qa != qb) return qa < qb;
		const auto t = (a ^ b);
		return t > eps;
	}
};

struct L {
	P p, v;
	int ori (letp &a) const {return v.ori(a - p);}
	P inter(letl &l) const {return p + v * ((l.v ^ (p - l.p)) / (v ^ l.v));}
	double dis(letp &a) const {return abs(v ^ (a - p)) / abs(v);}
};

bool para(letl &p, letl &q) {return z(p.v ^ q.v);}

struct Polygon {
	vector<P> p;
	Polygon(const vector<P> &p = {}) : p(p) {}
	size_t nxt(const size_t i) const {return i == p.size() - 1 ? 0 : i + 1;}
	size_t pre(const size_t i) const {return i == 0 ? p.size() - 1 : i - 1;}
	T double_area() const {
		T sum = 0;
		for (size_t i = 0; i < p.size(); ++i) sum += (p[i] ^ p[nxt(i)]);
		return abs(sum);
	}
	double area() const {return double_area() / 2.0;}
};

struct C : Polygon {
	C (const vector<P> &p = {}) : Polygon(p) {}
};

vector<L> halfInter(vector<L> l, lett lim = 1e9) {
	const auto check = [](letl &a, letl &b, letl &c) {return a.ori(b.inter(c)) < 0;};
	
	const auto cmp = [] (letl &a, letl &b) {
		if (abs(a.v ^ b.v) <= eps && (a.v | b.v) >= -eps) return a.ori(b.p) == -1;
		return argcmp()(a.v, b.v);
	};
	l.push_back({{0, 0}, {0, -1}}); l.push_back({{0, 0}, {1, 0}});
	l.push_back({{lim, 0}, {0, 1}}); l.push_back({{0, lim}, {-1, 0}});
	sort(l.begin(), l.end(), cmp);
	deque<L> q;
	for (size_t i = 0; i < l.size(); ++i) {
		//printf("(%.2lf %.2lf) -> (%.2lf %.2lf)\n", l[i].p.x, l[i].p.y, l[i].v.x, l[i].v.y);
		if (i && l[i - 1].v.ori(l[i].v) == 0 && (l[i - 1].v | l[i].v) > eps) continue;
		while (q.size() > 1 && check(l[i], q.back(), q[q.size() - 2])) q.pop_back();
		while (q.size() > 1 && check(l[i], q[0], q[1])) q.pop_front();
		if (!q.empty() && q.back().v.ori(l[i].v) <= 0) return vector<L>();
		q.push_back(l[i]);
	}
	while (q.size() > 1 && check(q[0], q.back(), q[q.size() - 2])) q.pop_back();
	while (q.size() > 1 && check(q.back(), q[0], q[1])) q.pop_front();
	return vector<L>(q.begin(), q.end());
}

C halfInterConvex(vector<L> l, lett lim = 1e9) {
	l = halfInter(l, lim);
	vector<P> res; res.resize(l.size());
	for (size_t i = 0; i < l.size(); ++i)
		res[i] = l[i].inter(l[i == l.size() - 1 ? 0 : i + 1]);
	return res;
}

#define N 4007

int a[N], b[N], c[N];

inline void work() {
	int n = rd(), m = rd();
	for (int i = 1; i <= n; ++i) {
		a[i] = rd(); b[i] = rd(); c[i] = rd();
	}
	if (n >= 3) {puts("100.000000%"); return;}
	if (n == 2) {
		L l1, l2;
		if (a[1] != 0)l1.p = P{-1.0 * c[1] / a[1], 0};
		else l1.p = P{0.0, -1.0 * c[1] / b[1]};
		l1.v = P{-b[1], a[1]};
		if (a[2] != 0)l2.p = P{-1.0 * c[2] / a[2], 0};
		else l2.p = P{0.0, -1.0 * c[2] / b[2]};
		l2.v = P{-b[2], a[2]};
		if (para(l1, l2)) {puts("100.000000%"); return;}
		P pos = l1.inter(l2);
		if (abs(pos.x) >= m || abs(pos.y) >= m) {puts("100.000000%"); return;}
		vector<L> sl(2);
		sl[0] = l1; sl[1] = l2;
		double mn = 1e18;
		mn = min(mn, halfInterConvex(sl, m).area());
		//printf("%.10lf\n", mn);
		sl[0].v = -sl[0].v;
		mn = min(mn, halfInterConvex(sl, m).area());
		//printf("%.10lf\n", mn);
		sl[1].v = -sl[1].v;
		mn = min(mn, halfInterConvex(sl, m).area());
		//printf("%.10lf\n", mn);
		sl[0].v = -sl[0].v;
		mn = min(mn, halfInterConvex(sl, m).area());
		//printf("%.10lf\n", mn);
		printf("%.6lf", 100 * (1.0 - mn / m / m));
		puts("%");
	}
	if (n == 1) {
		vector<L> sl(1);
		if (a[1] != 0) sl[0].p = P{-1.0 * c[1] / a[1], 0};
		else sl[0].p = P{0.0, -1.0 * c[1] / b[1]};
		sl[0].v = P{-b[1], a[1]};
		double mn = 1e18;
		mn = min(mn, halfInterConvex(sl, m).area());
		//printf("%.10lf\n", mn);
		sl[0].v = -sl[0].v;
		mn = min(mn, halfInterConvex(sl, m).area());
		//printf("%.10lf\n", mn);
		printf("%.6lf", 100 * (1.0 - mn / m / m));
		puts("%");
	}
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;	
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3748kb

input:

1
2 1000
0 1 -750
1 0 -750

output:

93.750000%

result:

ok OK!

Test #2:

score: 0
Accepted
time: 3ms
memory: 3792kb

input:

500
1 1000
1 0 -300
1 1000
1 1 -500
1 1000
1 1 -1000
1 2
0 -1 1
1 1
-1 -1 1
1 1000
-866 287 1
1 1
3 -442 1
1 130
-628 558 0
1 868
-297 166 1
1 479
373 3 -96709
1 68
527 -833 0
1 348
-337 954 -109611
1 917
564 2 -449502
1 16
679 -175 0
1 463
138 -961 3
1 361
-951 -12 45113
1 464
-977 622 -35388
1 351...

output:

70.000000%
87.500000%
50.000000%
50.000000%
50.000000%
83.429446%
99.434389%
55.573248%
72.053484%
53.725926%
68.367347%
50.678631%
86.735384%
87.113402%
92.819305%
87.490351%
75.495542%
99.939269%
79.498817%
99.791156%
100.000000%
99.967926%
71.862629%
87.212627%
99.999999%
52.507599%
95.787352%
98...

result:

ok OK!

Test #3:

score: 0
Accepted
time: 3ms
memory: 3664kb

input:

50
4000 1000
-866 287 1
-246 141 188157
994 0 -948594
3 -442 1
172 -257 2
-77 -628 557282
-983 -297 165987
-172 -992 4695
961 587 -844056
-981 631 897222
289 1 -184824
-463 493 -336717
954 -110 32323
67 866 -240824
893 -111 -546885
259 -818 385562
906 93 -191311
308 -794 258487
502 -855 -273835
-649...

output:

100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
...

result:

ok OK!