#include <bits/stdc++.h>
#include "nice_lines.h"
using namespace std;
#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)
template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if(0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 100;
const int MAXA = 10000;
const ld EPS = 1e-12;
const ld STEP = 1e-5;
struct Point {
long double x, y;
Point();
Point(long double x, long double y);
Point operator-() const;
Point& operator+=(const Point &p);
Point& operator-=(const Point &p);
Point operator+(const Point &p) const;
Point operator-(const Point &p) const;
Point operator* (long double k) const;
long double dot(const Point &p) const;
};
struct Line {
Point off, dir;
Line(int a, int b);
long double dist(Point p);
};
Point::Point(): x(0), y(0) {}
Point::Point(long double x, long double y): x(x), y(y) {}
Point Point::operator-() const{
return Point(-x, -y);
}
Point& Point::operator+=(const Point &p) {
x += p.x;
y += p.y;
return *this;
}
Point& Point::operator-=(const Point &p) {
return *this += (-p);
}
Point Point::operator+(const Point &p) const {
Point res = *this;
return res += p;
}
Point Point::operator-(const Point &p) const {
Point res = *this;
return res -= p;
}
long double Point::dot(const Point &p) const {
return x * p.x + y * p.y;
}
Point Point::operator* (long double k) const {
return Point(x * k, y * k);
}
Line::Line(int a, int b) {
off = Point(0, b);
dir = Point(1, a);
}
long double Line::dist(Point p) {
p -= off;
Point delta = dir * (p.dot(dir) / dir.dot(dir)) - p;
return sqrt(delta.dot(delta));
}
ld mp0[MAXA * 4 + 5];
ld query0(int x) {
if (mp0[x + MAXA] != LINF) {
return mp0[x + MAXA];
}
return mp0[x + MAXA] = query(0, x);
}
int fib[MAXA];
void solve(int subtask_id, int n) {
REP (i, 0, MAXA * 2) {
mp0[i] = LINF;
}
vi va, vb;
vector<Line> vl;
int blo = -MAXA, bhi = MAXA;
if (subtask_id == 4) {
blo = -500, bhi = 500;
}
fib[0] = 1; fib[1] = 2;
int gd = -1;
REP (i, 2, MAXA) {
fib[i] = fib[i - 1] + fib[i - 2];
if (blo + fib[i] >= bhi) {
bhi = blo + fib[i];
gd = i;
break;
}
}
REP (i, 0, n) {
int lo = blo, hi = bhi;
RREP (k, gd, 2) {
//while (hi - lo >= 3) {
//int mid1 = lo + (hi - lo) / 3, mid2 = lo + (hi - lo) / 3 * 2;
int mid1 = lo + fib[k - 2], mid2 = lo + fib[k - 1];
ld q1 = query0(mid1), q2 = query0(mid2);
cerr << mid1 << ": " << q1 << '\n';
cerr << ' ' << mid2 << ": " << q2 << '\n';
for (Line l : vl) {
q1 -= l.dist(Point(0, mid1));
q2 -= l.dist(Point(0, mid2));
}
//cerr << mid1 << ": " << q1 << '\n';
//cerr << ' ' << mid2 << ": " << q2 << '\n';
if (q1 < q2) {
hi = mid2;
} else {
lo = mid1;
}
}
int b = INF;
ld mn = LINF;
REP (i, lo, hi + 1) {
ld q = query0(i);
for (Line l : vl) {
q -= l.dist(Point(0, i));
}
if (mnto(mn, q)) {
b = i;
}
}
//assert(b != INF);
lo = -MAXA, hi = MAXA;
if (subtask_id == 4) {
lo = -500, hi = 500;
}
while (hi - lo >= 3) {
int mid1 = lo + (hi - lo) / 3, mid2 = lo + (hi - lo) / 3 * 2;
ld q1 = query(STEP, mid1 * STEP + b), q2 = query(STEP, mid2 * STEP + b);
//cerr << mid1 << ' ' << mid1 * STEP + b << ": " << q1 << '\n';
//cerr << ' ' << mid2 << ' ' << mid2 * STEP + b << ": " << q2 << '\n';
for (Line l : vl) {
q1 -= l.dist(Point(STEP, mid1 * STEP + b));
q2 -= l.dist(Point(STEP, mid2 * STEP + b));
}
if (q1 < q2) {
hi = mid2;
} else {
lo = mid1;
}
}
int a = INF;
mn = LINF;
REP (i, lo, hi + 1) {
ld q = query(STEP, i * STEP + b);
for (Line l : vl) {
q -= l.dist(Point(STEP, i * STEP + b));
}
if (mnto(mn, q)) {
a = i;
}
}
//assert(a != INF);
va.pb(a); vb.pb(b);
vl.pb(Line(a, b));
}
the_lines_are(va, vb);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
620 KB |
Output is correct |
| 2 |
Correct |
2 ms |
592 KB |
Output is correct |
| 3 |
Correct |
2 ms |
592 KB |
Output is correct |
| 4 |
Correct |
1 ms |
592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
592 KB |
Output is correct |
| 2 |
Correct |
4 ms |
592 KB |
Output is correct |
| 3 |
Correct |
4 ms |
620 KB |
Output is correct |
| 4 |
Correct |
2 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
592 KB |
Output is correct |
| 2 |
Correct |
3 ms |
592 KB |
Output is correct |
| 3 |
Correct |
3 ms |
592 KB |
Output is correct |
| 4 |
Correct |
3 ms |
592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
75 ms |
592 KB |
Output is partially correct |
| 2 |
Partially correct |
84 ms |
624 KB |
Output is partially correct |
| 3 |
Partially correct |
57 ms |
636 KB |
Output is partially correct |
| 4 |
Partially correct |
124 ms |
592 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
640 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
75 ms |
592 KB |
Output is partially correct |
| 2 |
Partially correct |
84 ms |
624 KB |
Output is partially correct |
| 3 |
Partially correct |
57 ms |
636 KB |
Output is partially correct |
| 4 |
Partially correct |
124 ms |
592 KB |
Output is partially correct |
| 5 |
Incorrect |
30 ms |
640 KB |
Incorrect |
| 6 |
Halted |
0 ms |
0 KB |
- |
