| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 647096 | danikoynov | Nicelines (RMI20_nicelines) | 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.
/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
#include "nice_lines.h"
using namespace std;
typedef long long ll;
int V = 1e4 + 10;
struct point
{
long double x, y;
point(long double _x = 0, long double _y = 0)
{
x = _x;
y = _y;
}
};
struct line
{
point A, B;
long double k, m;
line(point _A, point _B)
{
A = _A;
B = _B;
k = (B.y - A.y) / (B.x - A.x);
/// k * A.x + m = A.y
m = A.y - A.x * k;
}
bool operator < (const line &l) const
{
return k < l.k;
}
};
point intersection(line l1, line l2)
{
long double x = (l2.m - l1.m) / (l1.k - l2.k), y = l1.k * x + l1.m;
return point(x, y);
}
vector < line > cur;
long double cross(long double x)
{
for (int a = -V; a <= V; a ++)
{
long double lf = x - (long double)(3 * V * a);
if (abs(lf) <= V)
return a;
}
return 1e9;
}
bool same(line l1, line l2)
{
///cout << abs(l1.k - l2.k) << " " << abs(l1.m - l2.m) << endl;
if (abs(l1.k - l2.k) < eps)
return true;
return false;
}
void divide(line l1, line l2)
{
///cout << l1.k << " " << l1.m << " " << l2.k << " " << l2.m << endl;
point p = intersection(l1, l2);
long double cr = cross(p.x);
if (cr == 1e9)
{
point p1(p.x, query(3 * V, p.x));
point p2(p.x + 1, query(3 * V, p.x + 1));
line l3(p1, p2);
cur.push_back(l3);
divide(l1, l3);
divide(l3, l2);
return;
}
else
{
long double t1 = (long double)(3 * V) * cr - V - 1;
long double t2 = (long double)(3 * V) * cr + V + 1;
point p1(t1, query(3 * V, t1));
line l3(p1, p);
/**cout << l3.k << " " << l3.m << endl;
cout << l1.k << " " << l1.m << endl;
cout << t1 << " " << t2 << endl;*/
///cout << l1.k << " " << l3.k << endl;
if (!same(l1, l3))
{
///exit(0);
point df(t1 + 1, query(3 * V, t1 + 1));
line dl(p1, df);
cur.push_back(dl);
divide(l1, dl);
divide(dl, l2);
return;
}
///cout << "here" << endl; exit(0);
point p2(t2, query(3 * V, t2));
line l4(p, p2);
if (!same(l2, l4))
{
point df(t2 - 1, query(3 * V, t2 - 1));
line dl(df, p2);
cur.push_back(dl);
divide(l1, dl);
divide(dl, l2);
return;
}
}
}
void solve(int subtask_id, int N)
{
if (subtask_id == 4)
V = 510;
point A1(3 * V * V, query(3 * V, 3 * V * V)), B1(3 * V * V + 1, query(3 * V, 3 * V * V + 1));
line l1(A1, B1);
point A2(- 3 * V * V, query(3 * V, - 3 * V * V)), B2(- 3 * V * V + 1, query(3 * V, - 3 * V * V + 1));
line l2(A2, B2);
cur.push_back(l1);
cur.push_back(l2);
divide(l2, l1);
vector < long double > it;
sort(cur.begin(), cur.end());
for (int i = 1; i < cur.size(); i ++)
{
it.push_back(intersection(cur[i - 1], cur[i]).x);
}
vector < int > a;
vector < int > b;
for (int i = 0; i < it.size(); i ++)
{
for (int pa = -V; pa <= V; pa ++)
{
long double lf = it[i] - (long double)(3 * V * pa);
if (abs(lf) <= V)
{
a.push_back(pa);
b.push_back(round(lf));
break;
}
}
}
the_lines_are(a, b);
}