oj.uz

Submission #603347

# Submission time Handle Problem Language Result Execution time Memory
603347 2022-07-24T03:56:15 Z Zanite Svjetlost (COI18_svjetlost) C++17
40 / 100
 3000 ms 15868 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB 11 numbers
2 Correct 1 ms 212 KB 41 numbers
3 Correct 1 ms 340 KB 11 numbers
4 Correct 2 ms 340 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB 11 numbers
2 Correct 1 ms 212 KB 41 numbers
3 Correct 1 ms 340 KB 11 numbers
4 Correct 2 ms 340 KB 93 numbers
5 Correct 28 ms 468 KB 101 numbers
6 Correct 236 ms 728 KB 1201 numbers
7 Correct 377 ms 688 KB 1556 numbers
8 Correct 554 ms 936 KB 1996 numbers
9 Correct 504 ms 816 KB 1960 numbers
10 Correct 543 ms 704 KB 1991 numbers
11 Correct 554 ms 788 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB found '32934.3604541190', expected '32934.3604541195', error '0.0000000000'
2 Correct 2 ms 596 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 9 ms 2256 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 15 ms 4040 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 66 ms 15868 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 65 ms 15816 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 832 KB 1001 numbers
2 Execution timed out 3079 ms 4812 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB 11 numbers
2 Correct 1 ms 212 KB 41 numbers
3 Correct 1 ms 340 KB 11 numbers
4 Correct 2 ms 340 KB 93 numbers
5 Correct 28 ms 468 KB 101 numbers
6 Correct 236 ms 728 KB 1201 numbers
7 Correct 377 ms 688 KB 1556 numbers
8 Correct 554 ms 936 KB 1996 numbers
9 Correct 504 ms 816 KB 1960 numbers
10 Correct 543 ms 704 KB 1991 numbers
11 Correct 554 ms 788 KB 1963 numbers
12 Correct 0 ms 312 KB found '32934.3604541190', expected '32934.3604541195', error '0.0000000000'
13 Correct 2 ms 596 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 9 ms 2256 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 15 ms 4040 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 66 ms 15868 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 65 ms 15816 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 593 ms 832 KB 1001 numbers
19 Execution timed out 3079 ms 4812 KB Time limit exceeded
20 Halted 0 ms 0 KB -