oj.uz

Submission #144568

# Submission time Handle Problem Language Result Execution time Memory
144568 2019-08-17T08:29:24 Z emilem Svjetlost (COI18_svjetlost) C++14
40 / 100
 3000 ms 4516 KB 
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <vector>
typedef long long llong;
typedef long double ldouble;

inline bool AreParallel(llong x1, llong y1, llong x2, llong y2, llong x3, llong y3, llong x4, llong y4)
{
	return /*std::abs*/((x2 - x1) * (y4 - y3)) == /*std::abs*/((x4 - x3) * (y2 - y1));
}
inline std::pair<ldouble, ldouble> Equation(ldouble x1, ldouble y1, ldouble x2, ldouble y2)
{
	ldouble k = (y2 - y1) / (x2 - x1);
	ldouble b = y1 - k * x1;
	return std::make_pair(k, b);
}
inline bool IntersectsRay(int rayX1, int rayY1, int rayX2, int rayY2, int x1, int y1, int x2, int y2)
{
	if (AreParallel(rayX1, rayY1, rayX2, rayY2, x1, y1, x2, y2))
		return false;
	ldouble x, y;
	if ((rayX1 == rayX2 || rayY1 == rayY2) && (y1 == y2 || x1 == x2))
	{
		if (x1 == x2)
		{
			x = x1;
			y = rayY1;
		}
		else
		{
			x = rayX1;
			y = y1;
			return rayY1 - y > 0 != rayY2 - rayY1 > 0;
		}
	}
	else
	{
		std::pair<ldouble, ldouble> equation1 = Equation(rayX1, rayY1, rayX2, rayY2);
		std::pair<ldouble, ldouble> equation2 = Equation(x1, y1, x2, y2);
		ldouble k1 = equation1.first, b1 = equation1.second, k2 = equation2.first, b2 = equation2.second;
		if (rayX1 == rayX2)
		{
			x = rayX1;
			y = k2 * x + b2;
		}
		else if (x1 == x2)
		{
			x = x1;
			y = k1 * x + b1;
		}
		else
		{
			x = (b1 != b2 ? (b2 - b1) / (k1 - k2) : 0);
			y = k1 * x + b1;
		}
	}
	if (fabs(rayX1 - x) <= 0.0000001L) // ADD EPSILON
		return false;
	return rayX1 - x > 0 != rayX2 - rayX1 > 0;
}
inline ldouble Dist(int x1, int y1, int x2, int y2)
{
	return std::sqrt(ldouble(x2 - x1) * ldouble(x2 - x1) + ldouble(y2 - y1) * ldouble(y2 - y1));
}
void Solve(const std::vector<int>& x, const std::vector<int>& y)
{
	using namespace std;
	int n = x.size();
	vector<int> upto(n);
	for (int i = 0; i < n; ++i)
	{
		upto[i] = (i ? upto[i - 1] : (i + 1) % n);
		for (int j = (upto[i] + 1) % n; ; j = (j + 1) % n)
		{
			if (IntersectsRay(x[i], y[i], x[(i + 1) % n], y[(i + 1) % n],
				x[j], y[j], x[(j - 1 + n) % n], y[(j - 1 + n) % n]))
				upto[i] = j;
			else
				break;
		}
	}
	vector<ldouble> ans(n);
	for (int i = 0; i < n; ++i)
	{
		ans[i] = i ? ans[i - 1] - Dist(x[i - 1], y[i - 1], x[i], y[i]) : 0.;
		if (i && upto[i] == upto[i - 1])
			continue;
		for (int j = i ? (upto[i - 1] + 1) % n : (i + 1) % n; ; j = (j + 1) % n)
		{
			ans[i] += Dist(x[(j - 1 + n) % n], y[(j - 1 + n) % n], x[j], y[j]);
			if (j == upto[i])
				break;
		}
	}
	cout << fixed << setprecision(7) << *max_element(ans.begin(), ans.end()) << endl;
}
int main()
{
	using namespace std;
	int n;
	cin >> n;
	vector<int> stx(n), sty(n);
	for (int i = 0; i < n; ++i)
		cin >> stx[i] >> sty[i];
	int q;
	cin >> q;
	Solve(stx, sty);
	vector<bool> del(n, false);
	while (q--)
	{
		vector<int> x, y;
		int i;
		cin >> i; --i;
		del[i] = true;
		for (int j = 0; j < n; ++j)
			if (!del[j])
			{
				x.push_back(stx[j]);
				y.push_back(sty[j]);
			}
		Solve(x, y);
	}

	char I;
	cin >> I;
}

Compilation message

svjetlost.cpp: In function 'bool IntersectsRay(int, int, int, int, int, int, int, int)':
svjetlost.cpp:35:21: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
    return rayY1 - y > 0 != rayY2 - rayY1 > 0;
           ~~~~~~~~~~^~~
svjetlost.cpp:61:19: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
  return rayX1 - x > 0 != rayX2 - rayX1 > 0;
         ~~~~~~~~~~^~~

Subtask #1
12.0 / 12.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB 11 numbers
2 Correct 2 ms 376 KB 41 numbers
3 Correct 2 ms 376 KB 11 numbers
4 Correct 3 ms 376 KB 93 numbers
5 Correct 18 ms 376 KB 101 numbers
6 Correct 144 ms 464 KB 1201 numbers
7 Correct 214 ms 504 KB 1556 numbers
8 Correct 333 ms 508 KB 1996 numbers
9 Correct 292 ms 632 KB 1960 numbers
10 Correct 310 ms 544 KB 1991 numbers
11 Correct 301 ms 632 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB found '32934.3604541000', expected '32934.3604541195', error '0.0000000000'
2 Correct 4 ms 376 KB found '31571636.3365448005', expected '31571636.3365447633', error '0.0000000000'
3 Correct 19 ms 632 KB found '31442617.6286691017', expected '31442617.6286691241', error '0.0000000000'
4 Correct 33 ms 936 KB found '31424400.0534065999', expected '31424400.0534067489', error '0.0000000000'
5 Correct 150 ms 4472 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 151 ms 4516 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 504 KB 1001 numbers
2 Execution timed out 3045 ms 2284 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB 11 numbers
2 Correct 2 ms 376 KB 41 numbers
3 Correct 2 ms 376 KB 11 numbers
4 Correct 3 ms 376 KB 93 numbers
5 Correct 18 ms 376 KB 101 numbers
6 Correct 144 ms 464 KB 1201 numbers
7 Correct 214 ms 504 KB 1556 numbers
8 Correct 333 ms 508 KB 1996 numbers
9 Correct 292 ms 632 KB 1960 numbers
10 Correct 310 ms 544 KB 1991 numbers
11 Correct 301 ms 632 KB 1963 numbers
12 Correct 2 ms 256 KB found '32934.3604541000', expected '32934.3604541195', error '0.0000000000'
13 Correct 4 ms 376 KB found '31571636.3365448005', expected '31571636.3365447633', error '0.0000000000'
14 Correct 19 ms 632 KB found '31442617.6286691017', expected '31442617.6286691241', error '0.0000000000'
15 Correct 33 ms 936 KB found '31424400.0534065999', expected '31424400.0534067489', error '0.0000000000'
16 Correct 150 ms 4472 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 151 ms 4516 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 332 ms 504 KB 1001 numbers
19 Execution timed out 3045 ms 2284 KB Time limit exceeded
20 Halted 0 ms 0 KB -