QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#597883 | #6412. Classical Geometry Problem | manizare | WA | 0ms | 3824kb | C++14 | 2.5kb | 2024-09-28 19:16:45 | 2024-09-28 19:16:45 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define all(a) a.begin(),a.end()
#define int long long
#define ld long double
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn =2e5 + 10 , mod = 998244353 , inf= 1e10 ;;
struct po{
ld a[3] ;
};
vector <pair<ld,po> > vec ;
void go(po a , ld d){
vec.pb({d , a}) ;
}
ld sq(ld f){
ld l= 0 , r =1e9 ;
rep(i , 1 , 100){
ld mid = (l+r)/(ld)2;
if((mid*mid) <= f){
l = mid ;
}else{
r = mid ;
}
}
return l ;
}
ld dis(po a, po b){
int ans =0 ;
rep(i , 0 ,2){
ans += abs(a.a[i]-b.a[i]) * abs(a.a[i]-b.a[i]) ;
}
return sq((ld)ans);
}
int is(po f){
bool ok =0 ;
rep(i , 0 ,2){
if(f.a[i] < 0 && f.a[i] > 255){
ok = 1;
}
}
return ok ;
}
void cp(po f1){
rep(i , 0, 2)cout << f1.a[i] << " ";
cout << "\n" ;
}
po st ;
void f(po x){
int s =0 ;
rep(i , 0, 2){
if(x.a[i] ==0 || x.a[i]==255){
s++;
}
}
if(s == 3){
go(x , dis(st , x));
return ;
}
if(s==2){
po x2 = x , x3 = x ;
rep(i ,0 ,2){
if(x.a[i]!=0 && x.a[i]!=255){
x2.a[i]=0 ;
x3.a[i]=255;
}
}
f(x2) ;
go(x3 , dis(x2 , x)) ;
return ;
}
if(s==1){
vector <int> vec ;
rep(i , 0 , 2){
if(x.a[i]!=0 && x.a[i]!=255){
vec.pb(i);
}
}
ld m = x.a[vec[1]]/x.a[vec[0]] ;
po f1 = x , f2 =x , k= x ;
k.a[vec[0]] = k.a[vec[1]] = 0 ;
f1.a[vec[0]] = 255 ;f2.a[vec[1]] = 255 ;
f2.a[vec[0]] = (ld)255/m ;f1.a[vec[1]] = (ld)255*m ;
if(is(f1) == 1)f1 = f2 ;
f(f1) ;
go(k , dis(f1 , x));
return ;
}
rep(i , 0 ,2){
po b ;
b.a[i] = 255 ;
rep(j , 0 ,2){
if(j == i)continue ;
ld m = x.a[j]/x.a[i] ;
b.a[j] = m*(ld)255 ;
}
if(is(b) == 0){
f(b);
go(st , dis(b , x)) ;
break ;
}
}
}
int ch(int x){
if(x==0)return 0;
return 255 ;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
rep(i , 0 ,2)st.a[i] = 0 ;
int T ;
cin >> T ;
while(T--){
po b;
rep(i ,0 ,2)cin >> b.a[i] ;
vec.clear() ;
f(b);
cout<<sz(vec) << "\n" ;
rep(i ,0 , sz(vec)-1){
po v = vec[i].S ; ld d = vec[i].F ;
rep(i ,0 ,2)cout << v.a[i] << " " ;
cout << setprecision(12) << d << "\n" ;
}
}
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3824kb
input:
3 105 255 175 174 174 174 0 0 0
output:
3 255 255 0 360.624458405 255 255 255 425 0 255 0 291.547594742 2 255 255 255 441.67295593 0 0 0 140.296115413 1 0 0 0 0
result:
wrong answer too far from the target: (48.844719, 255.000000, 48.844719) instead of (105, 255, 175) (test case 1)