Submission #742968

#	Time	Username	Problem	Language	Result	Execution time	Memory
742968		maomao90	Nicelines (RMI20_nicelines)	C++17	11 / 100	3 ms	464 KiB

nicelines

#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 ld EPS = 1e-9;

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));
}

void solve(int subtask_id, int n) {
    int lo = -10000, hi = 10000;
    while (hi - lo >= 3) {
        cerr << lo << ' ' << hi << '\n';
        int mid1 = lo + (hi - lo) / 3, mid2 = lo + (hi - lo) / 3 * 2;
        ld q1 = query(0, mid1), q2 = query(0, mid2);
        if (q1 < q2) {
            hi = mid2;
        } else {
            lo = mid1;
        }
    }
    int b = -1;
    REP (i, lo, hi + 1) {
        if (query(0, i) < EPS) {
            b = i;
        }
    }
    assert(b != -1);
    lo = -10000, hi = 10000;
    while (hi - lo >= 3) {
        int mid1 = lo + (hi - lo) / 3, mid2 = lo + (hi - lo) / 3 * 2;
        ld q1 = query(1, mid1 + b), q2 = query(1, mid2 + b);
        if (q1 < q2) {
            hi = mid2;
        } else {
            lo = mid1;
        }
    }
    int a = -1;
    REP (i, lo, hi + 1) {
        if (query(1, i + b) < EPS) {
            a = i;
        }
    }
    assert(a != -1);
    the_lines_are({a}, {b});
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27