QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56095#3001. Piece of CakeYaoBIG#AC ✓84ms101060kbC++1.8kb2022-10-16 22:44:452022-10-16 22:44:48

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-10-16 22:44:48]
  • Judged
  • Verdict: AC
  • Time: 84ms
  • Memory: 101060kb
  • [2022-10-16 22:44:45]
  • Submitted

answer

#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()

using namespace std;

template<class A> string to_string(A v) {
	bool first = 1;
	string res = "{";
	for (const auto &x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}

void debug_out() { cerr << endl; }
template<class Head, class... Tail> void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

template<class T>
struct Point {
	using P = Point;

	T x, y;
	P operator -(P b) const { return P{x - b.x, y - b.y}; }
	T cross(P b) const { return x * b.y - y * b.x; }
};


int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	using T = long double;
	using P = Point<T>;

	const int maxn = 2500;
	vector<vector<T>> binom(maxn + 1, vector<T>(maxn + 1));
	rep(i, 0, maxn) {
		binom[i][0] = 1;
		rep(j, 1, i) binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
	}
	debug(binom[maxn - 1][maxn / 2] / binom[maxn - 1][maxn / 2]);

	int n, k; cin >> n >> k;
	vector<P> as(n);
	for (auto &[x, y]: as) cin >> x >> y;


	T ans = 0;
	rep(i, 0, n - 1) {
		P a = as[i];
		P b = as[(i + 1) % n];
		ans += b.cross(a) / 2;
	}
	//debug(ans);
	
	rep(i, 0, n - 1) {
		P a = as[i];
		T sum = 0;
		rep(j, 1, n - 1) {
			P b = as[(i + j - 1) % n];
			P c = as[(i + j) % n];
			int cnt = n - (j + 1);
			if (n < k - 2) break;
			sum += (c - a).cross(b - a) / 2;
			ans -= binom[cnt][k - 2] / binom[n][k] * sum;
		}
	}
	
	printf("%.10f\n", (double) ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 16ms
memory: 100924kb

input:

3 3
-5.236334 -8.519438
-9.987847 -0.492878
-9.994555 0.329962

output:

1.9279463962

result:

ok found '1.9279464', expected '1.9279464', error '0.0000000'

Test #2:

score: 0
Accepted
time: 81ms
memory: 101048kb

input:

2496 3
-9.999961 0.028130
-9.999655 0.083151
-9.999641 0.084830
-9.999572 0.092537
-9.999474 0.102653
-9.999366 0.112678
-9.999329 0.115862
-9.998360 0.181104
-9.998033 0.198381
-9.997191 0.237035
-9.995264 0.307754
-9.993680 0.355494
-9.992454 0.388414
-9.992180 0.395407
-9.992030 0.399190
-9.99086...

output:

47.7145370705

result:

ok found '47.7145371', expected '47.7145371', error '0.0000000'

Test #3:

score: 0
Accepted
time: 67ms
memory: 101056kb

input:

2099 1049
-9.999906 0.043015
-9.999734 0.072371
-9.999721 0.074260
-9.999602 0.089189
-9.999407 0.108349
-9.999328 0.115856
-9.998818 0.153747
-9.998136 0.193060
-9.997663 0.216208
-9.997463 0.225142
-9.996961 0.246480
-9.995978 0.282576
-9.995847 0.287087
-9.995567 0.296415
-9.994353 0.335674
-9.99...

output:

267.9489554203

result:

ok found '267.9489554', expected '267.9489554', error '0.0000000'

Test #4:

score: 0
Accepted
time: 20ms
memory: 101056kb

input:

342 171
-9.998818 0.153747
-9.997917 0.202726
-9.997663 0.216208
-9.986909 0.482051
-9.977066 0.669980
-9.960055 0.892895
-9.943677 1.059735
-9.924803 1.223737
-9.922265 1.244011
-9.881584 1.527686
-9.871340 1.595884
-9.813970 1.916653
-9.787551 2.050325
-9.745125 2.243053
-9.683458 2.495799
-9.6678...

output:

266.6441933828

result:

ok found '266.6441934', expected '266.6441934', error '0.0000000'

Test #5:

score: 0
Accepted
time: 15ms
memory: 101060kb

input:

87 86
7.934712 5.851277
7.957370 5.901363
7.984885 5.912160
8.057904 5.888196
8.090706 5.871558
8.192155 5.734764
8.214245 5.702976
8.241768 5.663321
8.314438 5.556037
8.394960 5.433442
8.425523 5.386110
8.474268 5.308844
8.497539 5.271774
8.565648 5.160298
8.580590 5.135443
8.621362 5.066710
8.6895...

output:

3.2268546365

result:

ok found '3.2268546', expected '3.2268546', error '0.0000000'

Test #6:

score: 0
Accepted
time: 84ms
memory: 101056kb

input:

2496 2471
-9.999961 0.028130
-9.999655 0.083151
-9.999641 0.084830
-9.999572 0.092537
-9.999474 0.102653
-9.999366 0.112678
-9.999329 0.115862
-9.998360 0.181104
-9.998033 0.198381
-9.997191 0.237035
-9.995264 0.307754
-9.993680 0.355494
-9.992454 0.388414
-9.992180 0.395407
-9.992030 0.399190
-9.99...

output:

314.1572713142

result:

ok found '314.1572713', expected '314.1572713', error '0.0000000'

Test #7:

score: 0
Accepted
time: 74ms
memory: 100924kb

input:

2379 1903
0.001241 9.999987
0.003330 9.999997
0.007027 9.999997
0.015799 9.999987
0.018521 9.999982
0.034934 9.999938
0.040716 9.999917
0.046881 9.999888
0.053865 9.999854
0.055231 9.999847
0.061980 9.999806
0.069431 9.999758
0.077677 9.999698
0.080054 9.999679
0.094173 9.999552
0.100783 9.999492
0....

output:

28.5359095707

result:

ok found '28.5359096', expected '28.5359096', error '0.0000000'