QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#563035 | #7937. Fast XORting | Xiao_Nanniang | TL | 0ms | 0kb | C++17 | 2.7kb | 2024-09-14 00:44:30 | 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