#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;
~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
11 numbers |
| 2 |
Correct |
2 ms |
256 KB |
41 numbers |
| 3 |
Correct |
3 ms |
376 KB |
11 numbers |
| 4 |
Incorrect |
4 ms |
376 KB |
1st numbers differ - expected: '33410.7858975314', found: '62748.2381236000', error = '0.8780832728' |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
11 numbers |
| 2 |
Correct |
2 ms |
256 KB |
41 numbers |
| 3 |
Correct |
3 ms |
376 KB |
11 numbers |
| 4 |
Incorrect |
4 ms |
376 KB |
1st numbers differ - expected: '33410.7858975314', found: '62748.2381236000', error = '0.8780832728' |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 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 |
Incorrect |
41 ms |
888 KB |
1st numbers differ - expected: '31424400.0534067489', found: '62839552.9264504015', error = '0.9997057325' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
911 ms |
616 KB |
1001 numbers |
| 2 |
Execution timed out |
3025 ms |
1644 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
11 numbers |
| 2 |
Correct |
2 ms |
256 KB |
41 numbers |
| 3 |
Correct |
3 ms |
376 KB |
11 numbers |
| 4 |
Incorrect |
4 ms |
376 KB |
1st numbers differ - expected: '33410.7858975314', found: '62748.2381236000', error = '0.8780832728' |
