/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
#include "nice_lines.h"
using namespace std;
typedef long long ll;
using namespace std;
typedef long long ll;
int V = 1e4 + 10;
const long double eps = 1e-4;
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;
}
int _N;
void divide(line l1, line l2)
{
if (cur.size() == _N + 1)
return;
///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;
_N = N;
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);
}
Compilation message
nicelines.cpp: In function 'void divide(line, line)':
nicelines.cpp:83:20: warning: comparison of integer expressions of different signedness: 'std::vector<line>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
83 | if (cur.size() == _N + 1)
| ~~~~~~~~~~~^~~~~~~~~
nicelines.cpp: In function 'void solve(int, int)':
nicelines.cpp:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for (int i = 1; i < cur.size(); i ++)
| ~~^~~~~~~~~~~~
nicelines.cpp:161:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | for (int i = 0; i < it.size(); i ++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
328 KB |
Output is correct |
| 2 |
Correct |
6 ms |
336 KB |
Output is correct |
| 3 |
Correct |
8 ms |
332 KB |
Output is correct |
| 4 |
Correct |
5 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
208 KB |
Output is correct |
| 2 |
Correct |
5 ms |
208 KB |
Output is correct |
| 3 |
Correct |
6 ms |
316 KB |
Output is correct |
| 4 |
Correct |
3 ms |
308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
328 KB |
Output is correct |
| 2 |
Correct |
6 ms |
336 KB |
Output is correct |
| 3 |
Correct |
8 ms |
332 KB |
Output is correct |
| 4 |
Correct |
5 ms |
332 KB |
Output is correct |
| 5 |
Correct |
4 ms |
208 KB |
Output is correct |
| 6 |
Correct |
5 ms |
208 KB |
Output is correct |
| 7 |
Correct |
6 ms |
316 KB |
Output is correct |
| 8 |
Correct |
3 ms |
308 KB |
Output is correct |
| 9 |
Correct |
12 ms |
336 KB |
Output is correct |
| 10 |
Correct |
10 ms |
316 KB |
Output is correct |
| 11 |
Correct |
11 ms |
336 KB |
Output is correct |
| 12 |
Correct |
11 ms |
328 KB |
Output is correct |
