QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#395151#3001. Piece of Cakeohiostatescarlet#AC ✓947ms4116kbC++171.4kb2024-04-21 08:39:262024-04-21 08:39:27

Judging History

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

  • [2024-04-21 08:39:27]
  • 评测
  • 测评结果:AC
  • 用时:947ms
  • 内存:4116kb
  • [2024-04-21 08:39:26]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define L long long;
#ifdef LOCAL
#define dbg(x) cerr << "[" << (#x) << " = " << (x) << "]\n";
#else
#define dbg(x)
#endif
// g++ -std=c++17 -O2 -DLOCAL -o a a.cpp

double cross(vector<double> a, vector<double> b) {
  return a[0] * b[1] - a[1] * b[0];
}

double area(vector<vector<double>> arr) {
  double ans = cross(arr.back(), arr[0]);
  for (int i = 0; i + 1 < arr.size(); i++) {
    ans += cross(arr[i], arr[i + 1]);
  }
  return fabs(ans) / 2;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, select; cin >> n >> select;
  int k = n - select;
  vector<double> comp(k + 1, 1);
  if (comp.size() > 1) {
    comp[1] = double(k) * (n - k - 1) * (n - k) / (double(n) * (n - 1) * (n - 2));
    for (int y = 2; y < comp.size(); y++) {
      comp[y] = comp[y - 1] / (n - y - 1) * (k - y + 1);
    }
  }
  vector<vector<double>> p(n, vector<double>(2));
  for (int i = 0; i < n; i++) {
    cin >> p[i][0] >> p[i][1];
  }
  double total = area(p);
  for (int start = 0; start < n; start++) {
    double a = 0;
    vector<vector<double>> points = {p[start], {0, 0}, {p[(start + 1) % n]}};
    for (int y = 1; y < k + 1; y++) {
      int end = start + y + 1;
      points[1] = points[2];
      points[2] = p[end % n];
      a += area(points);
      total -= a * comp[y];
    }
  }
  cout << fixed << setprecision(10) << total << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3764kb

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: 947ms
memory: 4116kb

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: 0
Accepted
time: 321ms
memory: 4060kb

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

result:

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

Test #4:

score: 0
Accepted
time: 9ms
memory: 4100kb

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: 0ms
memory: 3924kb

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: 11ms
memory: 4096kb

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: 163ms
memory: 4036kb

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'