QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56093#3001. Piece of CakeYaoBIG#WA 56ms52104kbC++1.8kb2022-10-16 22:30:072022-10-16 22:30:10

Judging History

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

  • [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:30:10]
  • 评测
  • 测评结果:WA
  • 用时:56ms
  • 内存:52104kb
  • [2022-10-16 22:30:07]
  • 提交

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 = double;
	using P = Point<T>;

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

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

	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", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 56ms
memory: 52104kb

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.7145370706

result:

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

Test #3:

score: -100
Wrong Answer
time: 36ms
memory: 37880kb

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:

-nan

result:

wrong output format Expected double, but "-nan" found