QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#404951 | #3001. Piece of Cake | Lspeed# | AC ✓ | 30ms | 53392kb | C++14 | 4.1kb | 2024-05-05 02:34:18 | 2024-05-05 02:34:19 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'