Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define err(x) cerr << #x << " is " << x << '\n';
- using namespace std;
- typedef double ld;
- struct Vector{
- ld x, y;
- Vector(ld x_arg = 0, ld y_arg = 0):x(x_arg), y(y_arg) {}
- friend ostream& operator<<(ostream& os, const Vector& v){
- os << v.x << ' ' << v.y;
- return os;
- }
- };
- const int MAXN = 1e5;
- vector <Vector> fence;
- int holes[MAXN / 2], n;
- ld hl[MAXN / 2];
- ld len(Vector a, Vector b){return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));}
- int main(){
- cout.precision(20);
- int l, k;
- cin >> n >> l >> k;
- for (int i = 0; i < k; i++){
- cin >> holes[i];
- holes[i]--;
- }
- for (int i = 0; i < n; i++){
- int x, y;
- cin >> x >> y;
- fence.pb(Vector(x, y));
- }
- int pos = 0;
- ld l1 = 0, fz = 0;
- for (int i = 0; i < n;i++){
- if (i == holes[pos] && !pos){
- fz = l1;
- pos = (pos + 1) % k;
- l1 = 0;
- }
- else if (i == holes[pos]){
- hl[pos] = l1;
- pos = (pos + 1) % k;
- l1 = 0;
- }
- else{
- l1 += len(fence[i], fence[(i + 1) % n]);
- }
- }
- hl[0] = l1 + fz;
- ld s = 0, ans = 0;
- for (int hole_ind = 0;hole_ind < k;hole_ind++){
- s += len(fence[holes[hole_ind]], fence[(holes[hole_ind] + 1) % n]);
- int ind = hole_ind;
- ld nowl = l, ansn = 0;
- bool flag = false;
- while(nowl > 0 && !(flag && ind == hole_ind)){
- ld tmp = len(fence[holes[ind]], fence[(holes[ind] + 1) % n]);
- if (tmp > nowl){
- ansn += nowl;
- nowl = 0;
- }
- else{
- ansn += tmp;
- nowl -= tmp;
- }
- ind = (ind + 1) % k;
- nowl -= hl[ind];
- flag = true;
- }
- ans = max(ans, ansn);
- }
- cout << s - ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement