| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 144555 | emilem | Svjetlost (COI18_svjetlost) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#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(int x1, int y1, int x2, int y2)
{
ldouble k = ldouble(y2 - y1) / ldouble(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;
x = (k2 - k1) / (b1 - b2);
y = k1 * x + b1;
}
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));
}
int main()
{
using namespace std;
int n;
cin >> n;
vector<int> x(n), y(n);
for (int i = 0; i < n; ++i)
cin >> x[i] >> y[i];
int q;
cin >> q;
while (q--)
{
int temp;
cin >> temp;
}
// if q == 0
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 << ans << endl;
char I;
cin >> I;
}