oj.uz

Submission #144584

# Submission time Handle Problem Language Result Execution time Memory
144584 2019-08-17T08:58:32 Z emilem Svjetlost (COI18_svjetlost) C++14
40 / 100
 3000 ms 2808 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)
	{
		/*
		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 376 KB 11 numbers
2 Correct 3 ms 376 KB 41 numbers
3 Correct 3 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 3 ms 376 KB 41 numbers
3 Correct 3 ms 376 KB 11 numbers
4 Correct 3 ms 376 KB 93 numbers
5 Correct 18 ms 380 KB 101 numbers
6 Correct 143 ms 476 KB 1201 numbers
7 Correct 214 ms 484 KB 1556 numbers
8 Correct 332 ms 512 KB 1996 numbers
9 Correct 289 ms 484 KB 1960 numbers
10 Correct 310 ms 460 KB 1991 numbers
11 Correct 302 ms 584 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 20 ms 632 KB found '31442617.6286691017', expected '31442617.6286691241', error '0.0000000000'
4 Correct 33 ms 892 KB found '31424400.0534065999', expected '31424400.0534067489', error '0.0000000000'
5 Correct 149 ms 2808 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 149 ms 2680 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 3014 ms 1548 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 3 ms 376 KB 41 numbers
3 Correct 3 ms 376 KB 11 numbers
4 Correct 3 ms 376 KB 93 numbers
5 Correct 18 ms 380 KB 101 numbers
6 Correct 143 ms 476 KB 1201 numbers
7 Correct 214 ms 484 KB 1556 numbers
8 Correct 332 ms 512 KB 1996 numbers
9 Correct 289 ms 484 KB 1960 numbers
10 Correct 310 ms 460 KB 1991 numbers
11 Correct 302 ms 584 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 20 ms 632 KB found '31442617.6286691017', expected '31442617.6286691241', error '0.0000000000'
15 Correct 33 ms 892 KB found '31424400.0534065999', expected '31424400.0534067489', error '0.0000000000'
16 Correct 149 ms 2808 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 149 ms 2680 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 332 ms 504 KB 1001 numbers
19 Execution timed out 3014 ms 1548 KB Time limit exceeded
20 Halted 0 ms 0 KB -