Submission #967261

#TimeUsernameProblemLanguageResultExecution timeMemory
967261mdobricSvjetlost (COI18_svjetlost)C++11
14 / 100
24 ms3492 KiB
#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; 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 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; cout << fixed; cout << setprecision(6); cout << max_d << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...