oj.uz

답안 #743103

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743103 2023-05-17T08:05:10 Z maomao90 Nicelines (RMI20_nicelines) C++17
31 / 100
 68 ms 616 KB 
#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-1;

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 * 2 + 5];
ld query0(int x) {
    if (mp0[x + MAXA] != LINF) {
        return mp0[x + MAXA];
    }
    return mp0[x + MAXA] = query(0, x);
}

void solve(int subtask_id, int n) {
    REP (i, 0, MAXA * 2) {
        mp0[i] = LINF;
    }
    vi va, vb;
    vector<Line> vl;
    REP (i, 0, n) {
        int 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 = 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);
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 3 ms 592 KB Output is correct
3 Correct 3 ms 616 KB Output is correct
4 Correct 3 ms 592 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 592 KB Output is correct
2 Correct 5 ms 600 KB Output is correct
3 Correct 6 ms 592 KB Output is correct
4 Correct 4 ms 592 KB Output is correct

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 616 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 592 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 616 KB Incorrect
2 Halted 0 ms 0 KB -