oj.uz

Submission #144563

# Submission time Handle Problem Language Result Execution time Memory
144563 2019-08-17T08:15:59 Z emilem Svjetlost (COI18_svjetlost) C++14
12 / 100
 3000 ms 564 KB 
#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 + 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;
		}
	}
	ldouble ans = 0.;
	for (int i = 0; i < n; ++i)
	{
		ldouble curAns = 0.;
		for (int j = (i + 1) % n; ; j = (j + 1) % n)
		{
			curAns += Dist(x[(j - 1 + n) % n], y[(j - 1 + n) % n], x[j], y[j]);
			if (j == upto[i])
				break;
		}
		ans = max(ans, curAns);
	}
	cout << fixed << setprecision(7) << ans << 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:34:21: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
    return rayY1 - y > 0 != rayY2 - rayY1 > 0;
           ~~~~~~~~~~^~~
svjetlost.cpp:60: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 3 ms 376 KB 11 numbers
2 Correct 4 ms 376 KB 41 numbers
3 Correct 4 ms 376 KB 11 numbers
4 Correct 10 ms 256 KB 93 numbers

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB 11 numbers
2 Correct 4 ms 376 KB 41 numbers
3 Correct 4 ms 376 KB 11 numbers
4 Correct 10 ms 256 KB 93 numbers
5 Correct 2065 ms 376 KB 101 numbers
6 Execution timed out 3006 ms 376 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB found '32934.3604541000', expected '32934.3604541195', error '0.0000000000'
2 Correct 56 ms 376 KB found '31571636.3365448005', expected '31571636.3365447633', error '0.0000000000'
3 Execution timed out 3069 ms 456 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3020 ms 564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB 11 numbers
2 Correct 4 ms 376 KB 41 numbers
3 Correct 4 ms 376 KB 11 numbers
4 Correct 10 ms 256 KB 93 numbers
5 Correct 2065 ms 376 KB 101 numbers
6 Execution timed out 3006 ms 376 KB Time limit exceeded
7 Halted 0 ms 0 KB -