Submission #232920

#	Time	Username	Problem	Language	Result	Execution time	Memory
232920		shayan_p	Svjetlost (COI18_svjetlost)	C++14	40 / 100	3083 ms	2296 KiB

Main

// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

pll p[maxn];

ll operator * (pll a, pll b){
    return a.F * b.S - a.S * b.F;   
}
ll operator ^ (pll a, pll b){
    return a.F * b.F + a.S * b.S;
}
pll operator + (pll a, pll b){
    return {a.F + b.F, a.S + b.S};
}
pll operator - (pll a, pll b){
    return {a.F - b.F, a.S - b.S};
}

double lnn(pll a, pll b){
    return sqrt((a-b) ^ (a-b));
}

int n;
int nxt[maxn], bef[maxn];

void solve(int st){
    int l = st, r = st;
    double len = 0, ans = 0;
    do{
	if(r == l)
	    r = nxt[r], len+= lnn(p[l], p[r]);
	while(l != r && (p[nxt[l]] - p[l]) * (p[nxt[r]] - p[r]) > 0)
	    len+= lnn(p[r], p[nxt[r]]), r = nxt[r];
	ans = max(ans, len);
	len-= lnn(p[l], p[nxt[l]]);
	l = nxt[l];
    }while(l != st);
    cout << setprecision(7) << fixed << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    cin >> n;
    for(int i = 0; i < n; i++){
	cin >> p[i].F >> p[i].S;
	nxt[i] = (i+1) % n;
	bef[i] = (i+n-1) % n;
    }
    solve(0);
    int q;
    cin >> q;
    while(q--){
	int x;
	cin >> x;
	--x;
	int A = bef[x], B = nxt[x];
	bef[B] = A, nxt[A] = B;
	solve(A);
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31