QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#563035#7937. Fast XORtingXiao_NanniangTL 0ms0kbC++172.7kb2024-09-14 00:44:302024-09-14 00:44:30

Judging History

你现在查看的是最新测评结果

  • [2024-09-14 00:44:30]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-09-14 00:44:30]
  • 提交

answer

#include <iostream>
#include <ctime>
#include <cmath>
#include <iomanip>

#define ld long double

using namespace std;

struct Vector2 {
    ld x = 0;
    ld y = 0;
    Vector2 operator+(const Vector2& other) const {
        return { x + other.x, y + other.y };
    }
    Vector2 operator+=(const Vector2& other) {
        x += other.x;
        y += other.y;
        return *this;
    }
    Vector2 operator-(const Vector2& other) const {
        return { x - other.x, y - other.y };
    }
    Vector2 operator-=(const Vector2& other) {
        x -= other.x;
        y -= other.y;
        return *this;
    }
    Vector2 operator*(double other) const {
        return { x * other, y * other };
    }
    Vector2 operator/(double other) const {
        return { x / other, y / other };
    }
    ld Mod() const {
        return sqrt(x * x + y * y);
    }
};

ld Dis(const Vector2& a, const Vector2& b) {
    return (b - a).Mod();
}

Vector2 ChangeDis(const Vector2& a, ld dis) {
    return a * (dis / a.Mod());
}

int n;
int m;
Vector2 news[1010];
Vector2 olds[1010];

ld resDis = 2e6;
Vector2 res;

pair<Vector2, ld> CurAns() {
    Vector2 cur;
    ld curDis = 0;
    for (int i = 0; i < n; i++) {
        Vector2 node1 = news[i] + res;
        for (int j = 0; j < m; j++) {
            Vector2 newVec = node1 - olds[j];
            // cout << newVec << endl;
            ld newDis = newVec.Mod();
            // cout << i << ',' << j << ',' << newDis << endl;
            if (newDis > curDis) {
                cur = newVec;
                curDis = newDis;
            }
        }
    }
    // if (curDis) cout << curDis << endl;
    return { cur, curDis };
}

void Pashan() {
    Vector2 cur;
    tie(cur, resDis) = CurAns();
    ld maxDis = 1;
    while (clock() * 10ull < CLOCKS_PER_SEC * 19ull) {
        Vector2 curVec = cur * -maxDis;
        res += curVec;
        auto [cur2, curDis] = CurAns();
        if (curDis < resDis) {
            resDis = curDis;
            cur = cur2;
        }
        else {
            res -= curVec;
            // cout << "curDis = " << curDis << endl;
            // cout << "resDis = " << resDis << endl;
            // cout << "Wrong: maxDis = " << maxDis << endl;
        }
        maxDis *= 0.99;
    }
}

void Solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> news[i].x >> news[i].y;
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> olds[i].x >> olds[i].y;
    }
    // cout << CurAns().second << endl;
    Pashan();
    cout << setprecision(114514) << resDis << ' ' << res.x << ' ' << res.y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

8
0 1 3 2 5 4 7 6

output:


result: