Submission #603347

#	Time	Username	Problem	Language	Result	Execution time	Memory
603347		Zanite	Svjetlost (COI18_svjetlost)	C++17	40 / 100	3079 ms	15868 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using pii	= pair<int, int>;
using ll	= long long;
using pll	= pair<ll, ll>;
using ld	= long double;

#define fi	first
#define se	second

struct Point {
	ld x, y;
	Point() {}
	Point(ld x, ld y) : x(x), y(y) {}
};

ld angle(Point A, Point B) {return atan2((B.y - A.y), (B.x - A.x));}
ld dist(Point A, Point B) {return sqrt((A.y - B.y)*(A.y - B.y) + (A.x - B.x)*(A.x - B.x));}

ld _x, _y;

const int maxN	= 1e5 + 5;
const ld PI		= acos(-1);
const ld _2PI	= (ld)2 * PI;
const ld EPS	= 1e-9;

int n, q;
vector<Point> P(1);
bool deleted[maxN];

bool geq(ld x, ld y) {return (x-y >= -EPS);}

ld solve() {
	vector<int> active;
	for (int i = 1; i <= n; i++) {
		if (!deleted[i]) active.push_back(i);
	}
	int as = active.size();
	for (int i = 0; i < as; i++) {
		active.push_back(active[i]);
	}

	vector<ld> A = {-1000}, D(1);
	as = active.size();
	for (int i = 1; i < as; i++) {
		A.push_back(angle(P[active[i]], P[active[i-1]]));
		D.push_back(dist(P[active[i]], P[active[i-1]]));

		while (A[i] < A[i-1]) {A[i] += 2*PI;}
		D[i] += D[i-1];
	}

	/*
	for (auto i : A) {cout << i << ' ';} cout << '\n';
	for (auto i : D) {cout << i << ' ';} cout << '\n';
	cout << '\n';
	*/

	ld ans = 0;
	for (int i = 1; i < as; i++) {
		ld curAngle = A[i];
		int L = i+1, R = as-1, F = i;
		while (L <= R) {
			int M = (L + R) >> 1;
			if (geq(A[M], curAngle + PI)) {
				R = M - 1;
			} else {
				F = M;
				L = M + 1;
			}
		}
		ans = max(ans, D[F] - D[i-1]);
	}

	return ans;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%Lf %Lf", &_x, &_y);
		P.push_back(Point(_x, _y));
	}

	scanf("%d", &q);
	printf("%.9Lf\n", solve());
	for (int d, i = 1; i <= q; i++) {
		scanf("%d", &d);
		deleted[d] = 1;

		printf("%.9Lf\n", solve());
	}
}

Compilation message (stderr)

svjetlost.cpp: In function 'int main()':
svjetlost.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
svjetlost.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%Lf %Lf", &_x, &_y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
svjetlost.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%d", &d);
      |   ~~~~~^~~~~~~~~~

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