QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#660475 | #2950. Growing Some Oobleck | enze114514 | WA | 0ms | 3864kb | C++20 | 10.3kb | 2024-10-20 11:27:06 | 2024-10-20 11:27:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
const ld pi = 3.14159265358979323846;
const ll INF = 1e18;
template<typename T>
T chmax(T a, T b) {
return a > b ? a : b;
}
template<typename T>
T chmin(T a, T b) {
return a > b ? b : a;
}
template<typename T>
struct Point{
T x, y;
ld eps;
Point() : x(0), y(0), eps(1e-9) {}
Point(T x, T y) : x(x), y(y), eps(1e-9) {}
void set_eps(T eps){
this->eps = eps;
}
Point operator+ (const Point& b){
return Point(x + b.x, y + b.y);
}
Point operator- (const Point& b){
return Point(x - b.x, y - b.y);
}
Point operator- (){
return Point(-x, -y);
}
Point operator* (T t) const{
return Point(x * t, y * t);
}
Point operator/ (T t) const{
return Point(x / t, y / t);
}
Point &operator+=(Point p) &{
x += p.x;
y += p.y;
return *this;
}
Point &operator-=(Point p) &{
x -= p.x;
y -= p.y;
return *this;
}
Point &operator*=(T v) &{
x *= v;
y *= v;
return *this;
}
Point &operator/=(T v) &{
x /= v;
y /= v;
return *this;
}
Point &operator=(const Point& b) &{
x = b.x;
y = b.y;
return *this;
}
friend Point operator+ (const Point& a, const Point& b){
return {a.x + b.x, a.y + b.y};
}
friend Point operator- (const Point& a, const Point& b){
return {a.x - b.x, a.y - b.y};
}
friend bool operator==(Point a, Point b){
return a.x == b.x && a.y == b.y;
}
int sign(T x){
if(fabs(x) < eps){
return 0;
}
if(x < 0){
return -1;
}
return 1;
}
bool cmp(T x, T y){
if(fabs(x - y) > eps){
return 0;
}
return 1;
}
bool cmp(const Point& a, const Point& b){
return cmp(a.x, b.x) && cmp(a.y, b.y);
}
T dot(const Point& a, const Point& b){
return a.x * b.x + a.y * b.y;
}
T square(Point a){
return dot(a, a);
}
T cross(const Point& a, const Point& b){
return a.x * b.y - a.y * b.x;
}
T cross(const Point& a, const Point& b, const Point& p){
return (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
}
T get_len(const Point& a){
return sqrt(dot(a, a));
}
T get_angle(const Point& a, const Point& b){
return acos(dot(a, b) / get_len(a) / get_len(b));
}
T area(const Point& a, const Point& b, const Point& c){
return cross(b - a, c - a);
}
Point rotate(const Point& a, T angle){ //两个点就 b - a (b按a转)
T dx = a.x * cos(angle) + a.y * sin(angle);
T dy = -a.x * sin(angle) + a.y * cos(angle);
return Point(dx, dy);
}
Point intersect(const Point& p, const Point& v, const Point& q, const Point& w){
Point u = p - q;
T t = cross(w, u) / cross(v, w);
return p + v * t;
}
T point_dist(const Point& a, const Point& b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
T line_dist(const Point& a, const Point& b, const Point& p){
Point u = b - a, v = p - a;
return fabs(cross(u, v)) / get_len(u);
}
T get_slope(const Point& a, const Point& b){
if(b.y == a.y) return INF;
if(b.x == a.x) return 0;
return (b.y - a.y) / (b.x - a.x);
}
T circle_intersect(const Point& p1, const Point& p2, const T r1, const T r2){
ld d = sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
if(d > r1 + r2 || d + chmin(r1, r2) <= chmax(r1, r2)){
return 0;
}
else if(d == r1 + r2){
return 1;
}
else{
return 2;
}
}
T seg_dist(const Point& a, const Point& b, const Point& p){
if(a == b){
return get_len(p - a);
}
Point u = b - a, v = p - a, w = p - b;
if(sign(dot(u, v)) < 0){
return get_len(v);
}
if(sign(dot(u, w)) > 0){
return get_len(w);
}
return line_dist(a, b, p);
}
Point projection(const Point& a, const Point& b, const Point& p){
Point v = b - a;
return a + v * dot(v, p - a) / get_len(v);
}
bool on_segment(const Point& a, const Point& b, const Point& p){
bool u = sign(cross(p - a, p - b)) == 0;
bool v = sign(dot(p - a, p - b)) <= 0;
return u && v;
}
bool seg_intersection(const Point& a1, const Point& a2, const Point& b1, const Point& b2){
T c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
T c3 = cross(b2 - b1, a2 - b1), c4 = cross(b2 - b1, a1 - b1);
return sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0;
}
vector<Point> get_circle_intersection(const Point& p1, const Point& p2, const T r1, const T r2){
ld d = sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
Point bv = {(p2.x - p1.x) / d, (p2.y - p1.y) / d};
if(d >= r1 + r2){
return {};
}
else if(d + chmin(r1, r2) <= chmax(r1, r2)){
return {{INF, INF}};
}
else{
Point<T> center;
ld a = (r1 * r1 - r2 * r2 + d * d) / (2 * d);
ld b = (r2 * r2 - r1 * r1 + d * d) / (2 * d);
center.x = p1.x + a * bv.x;
center.y = p1.y + a * bv.y;
ld h = sqrt(r1 * r1 - a * a);
Point it1 = {center.x + h * bv.y, center.y - h * bv.x};
Point it2 = {center.x - h * bv.y, center.y + h * bv.x};
return {it1, it2};
}
}
ld circle_rad(const T r1, const T r2){
return sqrt(r1 * r1 + r2 * r2);
}
};
const int N = (int)1e3 + 1, M = N * 2;
int vis[N], n;
void dfs(vector<ld> &p, vector<vector<ld>> &a){
while (true) {
if (all_of(vis, vis + n, [](int v){ return v; })) {
return;
}
ld min_t = INF;
for(int i = 0; i < n; i++){
if(vis[i]) continue;
ld x = a[i][0], y = a[i][1], r = a[i][2];
Point<ld> p1 = {x, y}, p2 = {p[0], p[1]};
ld dist = p1.point_dist(p1, p2);
ld sum_r = r + p[2];
if(dist <= sum_r){
min_t = 0;
break;
}
else {
ld delta_r = a[i][3] + p[3];
ld time_to_touch = (dist - sum_r) / delta_r;
if(time_to_touch < min_t){
min_t = time_to_touch;
}
}
}
for(int i = 0; i < n; i++){
if(!vis[i]){
a[i][2] += a[i][3] * min_t;
}
}
p[2] += p[3] * min_t;
if(min_t == INF){
return;
}
bool anyNewMerges = true;
while(anyNewMerges){
anyNewMerges = false;
vector<int> mergedCircles;
for(int i = 0; i < n; i++){
if(!vis[i]){
ld x = a[i][0], y = a[i][1], r = a[i][2];
Point<ld> p1 = {x, y}, p2 = {p[0], p[1]};
ld dist = p1.point_dist(p1, p2);
ld sum_r = r + p[2];
if(dist <= sum_r){
vis[i] = 1;
mergedCircles.push_back(i);
anyNewMerges = true;
}
}
}
if(anyNewMerges){
int count = 1 + mergedCircles.size();
ld sumX = p[0], sumY = p[1];
ld totalArea = p[2] * p[2] * pi;
ld maxS = p[3];
for(int idx : mergedCircles){
ld x = a[idx][0], y = a[idx][1], r = a[idx][2], s = a[idx][3];
sumX += x;
sumY += y;
totalArea += r * r * pi;
maxS = max(maxS, s);
}
p[0] = sumX / count;
p[1] = sumY / count;
p[2] = sqrt(totalArea / pi);
p[3] = maxS;
}
}
}
}
void solve() {
cin >> n;
vector<vector<ld>> a(n, vector<ld>(4));
for(int i = 0; i < n; i++){
cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
}
ld min_t = INF;
int id1 = -1, id2 = -1;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
ld x1 = a[i][0], y1 = a[i][1], r1 = a[i][2];
ld x2 = a[j][0], y2 = a[j][1], r2 = a[j][2];
Point<ld> p1 = {x1, y1}, p2 = {x2, y2};
ld dist = p1.point_dist(p1, p2);
ld sum_r = r1 + r2;
if(dist <= sum_r){
ld time_to_touch = 0;
if(time_to_touch < min_t){
min_t = time_to_touch;
id1 = i;
id2 = j;
}
} else {
ld delta_r = a[i][3] + a[j][3];
ld time_to_touch = (dist - sum_r) / delta_r;
if(time_to_touch < min_t){
min_t = time_to_touch;
id1 = i;
id2 = j;
}
}
}
}
for(int i = 0; i < n; i++){
a[i][2] += a[i][3] * min_t;
}
memset(vis, 0, sizeof(vis));
vis[id1] = vis[id2] = 1;
ld dx = (a[id1][0] + a[id2][0]) / 2;
ld dy = (a[id1][1] + a[id2][1]) / 2;
ld area = a[id1][2] * a[id1][2] * pi + a[id2][2] * a[id2][2] * pi;
ld r = sqrt(area / pi);
ld s = max(a[id1][3], a[id2][3]);
vector<ld> p = {dx, dy, r, s};
dfs(p, a);
cout << setprecision(20) << fixed << p[0] << " " << p[1] << endl;
cout << setprecision(20) << fixed << p[2] << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3864kb
input:
3 10 10 5 1 24 10 7 1 16 2 2 1
output:
16.50000000000000000000 6.00000000000000000000 10.44030650891055017962
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
5 -5 0 1 1 6 0 1 1 0 7 1 1 0 -8 1 1 0 0 1 2
output:
1.18750000000000000000 -3.12500000000000000000 7.61677681312230480315
result:
ok 3 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
2 -1000000000 0 1 1 1000000000 0 1 1
output:
0.00000000000000000000 0.00000000000000000000 1414213562.37309504882432520390
result:
ok 3 numbers
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3768kb
input:
4 -100000000 -1000000000 1 2 1000000000 -1000000000 1 2 -1000000000 1000000000 1 3 1000000000 1000000000 1 3
output:
-137500000.00000000000000000000 500000000.00000000000000000000 1840816448.24323888751678168774
result:
wrong answer 1st numbers differ - expected: '225000000.0000000', found: '-137500000.0000000', error = '1.6111111'