#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, q;
long long a[maxn], b[maxn];
long long max_poc, max_kraj, max_smjer = 0;
double max_d;
int bio[maxn];
vector <int> dobri;
vector <double> ans;
int bio1[maxn], bio2[maxn];
double calc (int x, int y){
y = (y + n) % n;
double prvi = abs(a[x] - a[y]) * abs(a[x] - a[y]), drugi = abs(b[x] - b[y]) * abs(b[x] - b[y]);
return sqrt(prvi + drugi);
}
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 iduci (int tr){
if (bio1[tr] != -1){
return bio1[tr];
}
int tr2 = tr;
tr++;
tr = tr % n;
while (bio[tr] == 1){
tr++;
tr = tr % n;
}
return bio1[tr2] = tr;
}
int prosli (int tr){
if (bio2[tr] != -1){
return bio2[tr];
}
int tr2 = tr;
tr--;
tr = (tr + n) % n;
while (bio[tr] == 1){
tr--;
tr = (tr + n) % n;
}
return bio2[tr2] = tr;
}
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;
double 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];
//cout << "d " << d << endl;
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);
//cout << "dodaj " << kraj << " " << kraj + 1 << " " << calc(kraj, kraj + 1) << endl;
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 << " " << d << 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);
}
//cout << max_smjer << " " << max_poc << " " << max_kraj << endl;
ans.push_back(max_d);
int prvi = 0, zadnji = n - 1;
for (int i = 0; i < q; i++){
for (int j = 0; j < n; j++){
bio1[j] = -1, bio2[j] = -1;
}
int makni;
cin >> makni;
makni--;
bio[makni] = 1;
while (bio[prvi] == 1){
prvi = iduci(prvi);
}
while (bio[zadnji] == 1){
zadnji = prosli(zadnji);
}
d = calc(prvi, iduci(prvi)) + calc(iduci(prvi), iduci(iduci(prvi))), tx;
kraj = iduci(prvi);
max_poc = prvi, max_kraj = iduci(prvi), max_d = d;
for (int poc = prvi; poc < n; poc++){
if (bio[poc] == 0){
long long a1 = a[poc], b1 = b[poc], a2 = a[iduci(poc)], b2 = b[iduci(poc)];
//cout << "d " << d << endl;
do{
kraj = iduci(kraj);
long long a3 = a[kraj], b3 = b[kraj], a4 = a[iduci(kraj)], b4 = b[iduci(kraj)];
d = d + calc(kraj, iduci(kraj));
//cout << "dodaj " << kraj << " " << kraj + 1 << " " << calc(kraj, kraj + 1) << endl;
tx = ccw(a1, b1, a2, b2, a4 - a3 + a1, b4 - b3 + b1);
}while(tx > 0);
d = d - calc(kraj, iduci(kraj));
kraj = prosli(kraj);
if (d > max_d){
max_d = d;
max_poc = poc;
max_kraj = kraj;
}
//cout << poc << " " << kraj << " " << d << endl;
d = d - calc(poc, iduci(poc + 1));
}
}
kraj = prosli(zadnji);
d = calc(zadnji, prosli(zadnji)) + calc(prosli(zadnji), prosli(prosli(zadnji)));
//cout << d << endl;
for (int poc = zadnji; poc >= 0; poc--){
if (bio[poc] == 0){
long long a1 = a[poc], b1 = b[poc], a2 = a[prosli(poc)], b2 = b[prosli(poc)];
do{
kraj = prosli(kraj);
long long a3 = a[kraj], b3 = b[kraj], a4 = a[prosli(kraj)], b4 = b[prosli(kraj)];
d = d + calc(kraj, prosli(kraj));
tx = ccw(a1, b1, a2, b2, a4 - a3 + a1, b4 - b3 + b1);
//cout << "? " << poc << " " << kraj << " " << tx << endl;
//cout << a1 << " " << b1 << " " << a2 << " " << b2 << " " << a4 - a3 + a2 << " " << b4 - b3 + b2 << endl;
}while(tx < 0);
d = d - calc(kraj, prosli(kraj));
kraj = iduci(kraj);
if (d > max_d){
max_d = d;
max_poc = poc;
max_kraj = kraj;
max_smjer = 1;
}
//cout << poc << " " << kraj << " " << d << endl;
d = d - calc(poc, prosli(poc));
}
}
ans.push_back(max_d);
}
for (int i = 0; i < ans.size(); i++){
cout << fixed;
cout << setprecision(6);
cout << ans[i] << "\n";
}
return 0;
}
Compilation message
svjetlost.cpp: In function 'int main()':
svjetlost.cpp:129:74: warning: right operand of comma operator has no effect [-Wunused-value]
129 | d = calc(prvi, iduci(prvi)) + calc(iduci(prvi), iduci(iduci(prvi))), tx;
| ^
svjetlost.cpp:184:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for (int i = 0; i < ans.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
11 numbers |
| 2 |
Correct |
1 ms |
2396 KB |
41 numbers |
| 3 |
Correct |
1 ms |
2396 KB |
11 numbers |
| 4 |
Correct |
1 ms |
2396 KB |
93 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
11 numbers |
| 2 |
Correct |
1 ms |
2396 KB |
41 numbers |
| 3 |
Correct |
1 ms |
2396 KB |
11 numbers |
| 4 |
Correct |
1 ms |
2396 KB |
93 numbers |
| 5 |
Correct |
9 ms |
2392 KB |
101 numbers |
| 6 |
Correct |
80 ms |
2520 KB |
1201 numbers |
| 7 |
Correct |
125 ms |
2508 KB |
1556 numbers |
| 8 |
Correct |
204 ms |
2652 KB |
1996 numbers |
| 9 |
Correct |
164 ms |
2508 KB |
1960 numbers |
| 10 |
Correct |
170 ms |
2588 KB |
1991 numbers |
| 11 |
Correct |
165 ms |
2396 KB |
1963 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
found '32934.3604540000', expected '32934.3604541195', error '0.0000000000' |
| 2 |
Correct |
1 ms |
2392 KB |
found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000' |
| 3 |
Correct |
3 ms |
2516 KB |
found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000' |
| 4 |
Correct |
5 ms |
2480 KB |
found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000' |
| 5 |
Correct |
23 ms |
2908 KB |
found '3142086769.6889619827', expected '3142086769.6889681816', error '0.0000000000' |
| 6 |
Correct |
22 ms |
2904 KB |
found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000' |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
2512 KB |
1001 numbers |
| 2 |
Execution timed out |
3037 ms |
2640 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
11 numbers |
| 2 |
Correct |
1 ms |
2396 KB |
41 numbers |
| 3 |
Correct |
1 ms |
2396 KB |
11 numbers |
| 4 |
Correct |
1 ms |
2396 KB |
93 numbers |
| 5 |
Correct |
9 ms |
2392 KB |
101 numbers |
| 6 |
Correct |
80 ms |
2520 KB |
1201 numbers |
| 7 |
Correct |
125 ms |
2508 KB |
1556 numbers |
| 8 |
Correct |
204 ms |
2652 KB |
1996 numbers |
| 9 |
Correct |
164 ms |
2508 KB |
1960 numbers |
| 10 |
Correct |
170 ms |
2588 KB |
1991 numbers |
| 11 |
Correct |
165 ms |
2396 KB |
1963 numbers |
| 12 |
Correct |
1 ms |
2396 KB |
found '32934.3604540000', expected '32934.3604541195', error '0.0000000000' |
| 13 |
Correct |
1 ms |
2392 KB |
found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000' |
| 14 |
Correct |
3 ms |
2516 KB |
found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000' |
| 15 |
Correct |
5 ms |
2480 KB |
found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000' |
| 16 |
Correct |
23 ms |
2908 KB |
found '3142086769.6889619827', expected '3142086769.6889681816', error '0.0000000000' |
| 17 |
Correct |
22 ms |
2904 KB |
found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000' |
| 18 |
Correct |
178 ms |
2512 KB |
1001 numbers |
| 19 |
Execution timed out |
3037 ms |
2640 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
