QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#404951#3001. Piece of CakeLspeed#AC ✓30ms53392kbC++144.1kb2024-05-05 02:34:182024-05-05 02:34:19

Judging History

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

  • [2024-05-05 02:34:19]
  • 评测
  • 测评结果:AC
  • 用时:30ms
  • 内存:53392kb
  • [2024-05-05 02:34:18]
  • 提交

answer

#include <iostream>     // Input/output stream objects
#include <fstream>      // File stream objects
#include <sstream>      // String stream objects
#include <iomanip>      // Input/output manipulators
#include <string>       // String class and functions
#include <vector>       // Dynamic array
#include <list>         // Doubly linked list
#include <set>          // Set container
#include <map>          // Map container
#include <queue>        // Queue container
#include <stack>        // Stack container
#include <algorithm>    // Algorithms on sequences (e.g., sort, find)
#include <cmath>        // Mathematical functions
#include <ctime>        // Date and time functions
#include <cstdlib>      // General purpose functions (e.g., memory management)
#include <cstring>      // C-style string functions
#include <cctype>       // Character classification functions
#include <cassert>      // Assert function for debugging
#include <exception>    // Standard exceptions
#include <functional>   // Function objects
#include <iterator>     // Iterator classes
#include <limits>       // Numeric limits
#include <locale>       // Localization and internationalization
#include <numeric>      // Numeric operations (e.g., accumulate)
#include <random>       // Random number generators
#include <stdexcept>    // Standard exception classes
#include <typeinfo>     // Runtime type information
#include <utility>      // Utility components (e.g., std::pair)
#include <bitset>

using namespace std;

#define FOR(i, a, b) for(int i = a; i < (b); i++)
#define FORE(i, a, b) for(int i = a; i <= (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define x first 
#define y second
#define mp make_pair
#define PI 3.141592653
const double eps = 1e-9;

template<class T>
struct Point {
    typedef Point P;
    T x, y;
    explicit Point(T x=0, T y=0) : x(x), y(y) {}
    bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
    bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
    P& operator+=(P p) {x += p.x, y += p.y; return *this; }
    P& operator-=(P p) {x -= p.x, y -= p.y; return *this; }
    P& operator*=(P p) {x *= p.x, y *= p.y; return *this; }
    P& operator/=(P p) {x /= p.x, y /= p.y; return *this; }
    P operator+(P p) const { return P(x+p.x, y+p.y); }
    P operator-(P p) const { return P(x-p.x, y-p.y); }
    P operator*(P p) const { return P(x*p.x, y*p.y); }
    P operator/(P p) const { return P(x/p.x, y/p.y); }
    T dot(P p) const { return x*p.x + y*p.y; }
    T cross(P p) const { return x*p.y - y*p.x; }
    T cross(P a, P b) const { return (a-*this).cross(b-*this); }
    friend ostream& operator<<(ostream &os, P p) {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};

const int N = 2510;
int n, k;
vector<Point<double>> poly;
vector<vector<double>> sumtri(N, vector<double>(N, 0));


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n >> k;
    
    FOR (i, 0, n) {
        double tx, ty;
        cin >> tx >> ty;
        poly.push_back(Point<double>(tx, ty));
    }

    // anti-clockwise + lowest x & y first element
    reverse(poly.begin(), poly.end());
    auto it = min_element(poly.begin(), poly.end());
    rotate(poly.begin(), it, poly.end());

    double areapoly = 0;
    FORE (i, 1, n-2) areapoly += poly[0].cross(poly[i], poly[i+1]) / 2;

    // cout << "AREAPOLY: " << areapoly << endl;
    double stfrac = (double)((n-k)*(k-1)) / (double)((n-2)*(n-1)) * ((double)k / (double)n);
    // cout << stfrac << " " << (n-k) * (k-1) << endl;
    FOR (i, 0, n) {
        double curpolya = 0, curfrac = stfrac;
        for (int j = 1; j <= n-k; j++) { // skip j point from i
            curpolya += poly[i].cross(poly[(i+j)%n], poly[(i+j+1) % n]) / 2.0;
            // cout << "CUR I: " << i << " CUR J: " << j << " CURAREA: " << curpolya << " CURFRAC: " << curfrac << endl;
            areapoly -= (curfrac * curpolya);
            curfrac *= (double)(n - k - j) / (double)(n - j - 2);
        }
    }
    cout << fixed << setprecision(10) << areapoly << endl;
    return 0;
}

詳細信息

Test #1:

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

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: 30ms
memory: 53244kb

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: 20ms
memory: 53392kb

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

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: 3ms
memory: 53180kb

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

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

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'