oj.uz

Submission #144590

# Submission time Handle Problem Language Result Execution time Memory
144590 2019-08-17T09:06:34 Z emilem Svjetlost (COI18_svjetlost) C++14
40 / 100
 3000 ms 2712 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);
		int l = (i + 2) % n;
		int r = (l + n - 3);
		while (l <= r)
		{
			int m = l + (r - l) / 2;
			if (IntersectsRay(x[i], y[i], x[(i + 1) % n], y[(i + 1) % n],
				x[m % n], y[m % n], x[(m - 1 + n) % n], y[(m - 1 + n) % n]))
			{
				upto[i] = m % n;
				l = m + 1;
			}
			else
				r = m - 1;
		}
		/*
		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 256 KB 11 numbers
2 Correct 3 ms 376 KB 41 numbers
3 Correct 2 ms 376 KB 11 numbers
4 Correct 4 ms 256 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB 11 numbers
2 Correct 3 ms 376 KB 41 numbers
3 Correct 2 ms 376 KB 11 numbers
4 Correct 4 ms 256 KB 93 numbers
5 Correct 40 ms 376 KB 101 numbers
6 Correct 360 ms 580 KB 1201 numbers
7 Correct 527 ms 376 KB 1556 numbers
8 Correct 859 ms 632 KB 1996 numbers
9 Correct 863 ms 504 KB 1960 numbers
10 Correct 872 ms 640 KB 1991 numbers
11 Correct 858 ms 616 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB found '32934.3604541000', expected '32934.3604541195', error '0.0000000000'
2 Correct 5 ms 376 KB found '31571636.3365448005', expected '31571636.3365447633', error '0.0000000000'
3 Correct 23 ms 632 KB found '31442617.6286691017', expected '31442617.6286691241', error '0.0000000000'
4 Correct 41 ms 888 KB found '31424400.0534065999', expected '31424400.0534067489', error '0.0000000000'
5 Correct 190 ms 2708 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 186 ms 2712 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 520 KB 1001 numbers
2 Execution timed out 3039 ms 1544 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 256 KB 11 numbers
2 Correct 3 ms 376 KB 41 numbers
3 Correct 2 ms 376 KB 11 numbers
4 Correct 4 ms 256 KB 93 numbers
5 Correct 40 ms 376 KB 101 numbers
6 Correct 360 ms 580 KB 1201 numbers
7 Correct 527 ms 376 KB 1556 numbers
8 Correct 859 ms 632 KB 1996 numbers
9 Correct 863 ms 504 KB 1960 numbers
10 Correct 872 ms 640 KB 1991 numbers
11 Correct 858 ms 616 KB 1963 numbers
12 Correct 2 ms 376 KB found '32934.3604541000', expected '32934.3604541195', error '0.0000000000'
13 Correct 5 ms 376 KB found '31571636.3365448005', expected '31571636.3365447633', error '0.0000000000'
14 Correct 23 ms 632 KB found '31442617.6286691017', expected '31442617.6286691241', error '0.0000000000'
15 Correct 41 ms 888 KB found '31424400.0534065999', expected '31424400.0534067489', error '0.0000000000'
16 Correct 190 ms 2708 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 186 ms 2712 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 929 ms 520 KB 1001 numbers
19 Execution timed out 3039 ms 1544 KB Time limit exceeded
20 Halted 0 ms 0 KB -