#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, q;
long long a[maxn], b[maxn];
long long max_d = 0, max_poc, max_kraj, max_smjer = 0;
long long calc (int x, int y){
y = (y + n) % n;
return abs(a[x] - a[y]) * abs(a[x] - a[y]) + abs(b[x] - b[y]) * abs(b[x] - b[y]);
}
long long ccw (long long a1, long long b1, long long a2, long long b2, long long a3, long long b3){
return a1 * (b2 - b3) + a2 * (b3 - b1) + a3 * (b1 - b2);
}
int main (void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i] >> b[i];
}
cin >> q;
int kraj = 1;
long long d = calc(0, 1) + calc(1, 2), tx;
max_poc = 0, max_kraj = 1, max_d = d;
for (int poc = 0; poc < n; poc++){
long long a1 = a[poc], b1 = b[poc], a2 = a[(poc + 1) % n], b2 = b[(poc + 1) % n];
do{
kraj++;
kraj = kraj % n;
long long a3 = a[kraj], b3 = b[kraj], a4 = a[(kraj + 1) % n], b4 = b[(kraj + 1) % n];
d = d + calc(kraj, kraj + 1);
tx = ccw(a1, b1, a2, b2, a4 - a3 + a2, b4 - b3 + b2);
}while(tx > 0);
d = d - calc(kraj, kraj + 1);
kraj = kraj + n - 1;
kraj = kraj % n;
if (d > max_d){
max_d = d;
max_poc = poc;
max_kraj = kraj;
}
//cout << poc << " " << kraj << endl;
d = d - calc(poc, poc + 1);
}
kraj = n - 2;
d = calc(n - 1, n - 2) + calc(n - 2, n - 3);
for (int poc = n - 1; poc >= 0; poc--){
long long a1 = a[poc], b1 = b[poc], a2 = a[(poc - 1 + n) % n], b2 = b[(poc - 1 + n) % n];
do{
kraj = kraj + n - 1;
kraj = kraj % n;
long long a3 = a[kraj], b3 = b[kraj], a4 = a[(kraj - 1 + n) % n], b4 = b[(kraj - 1 + n) % n];
d = d + calc(kraj, kraj - 1);
tx = ccw(a1, b1, a2, b2, a4 - a3 + a2, b4 - b3 + b2);
}while(tx > 0);
d = d - calc(kraj, kraj - 1);
kraj++;
kraj = kraj % n;
if (d > max_d){
max_d = d;
max_poc = poc;
max_kraj = kraj;
max_smjer = 1;
}
d = d - calc(poc, poc - 1);
}
double ans_max = 0;
if (max_smjer == 0){
int i = max_poc - 1;
do{
i++;
if (i == n){
i = 0;
}
double ans = calc(i, i + 1);
ans_max += sqrt(ans);
}while (i != max_kraj);
}
else{
int i = max_poc + 1;
do{
i--;
if (i == -1){
i = n - 1;
}
double ans = calc(i, i - 1);
ans_max += sqrt(ans);
}while (i != max_kraj);
}
cout << fixed;
cout << setprecision(6);
cout << ans_max << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st numbers differ - expected: '34724.8554753593', found: '34055.3370020000', error = '0.0192806698' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st numbers differ - expected: '34724.8554753593', found: '34055.3370020000', error = '0.0192806698' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st numbers differ - expected: '32934.3604541195', found: '32250.7290860000', error = '0.0207573901' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
1st numbers differ - expected: '1042655967.3918291330', found: '1040528690.3511480093', error = '0.0020402483' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st numbers differ - expected: '34724.8554753593', found: '34055.3370020000', error = '0.0192806698' |
| 2 |
Halted |
0 ms |
0 KB |
- |
