QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#194943#7521. Find the Gapucup-team1951#TL 214ms3976kbC++172.4kb2023-09-30 23:50:572023-09-30 23:50:58

Judging History

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

  • [2023-09-30 23:50:58]
  • 评测
  • 测评结果:TL
  • 用时:214ms
  • 内存:3976kb
  • [2023-09-30 23:50:57]
  • 提交

answer

// g++-13 3.cpp -std=c++17 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
 
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;
 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

using T = tuple<ld,ld,ld>;

ld g(int n,vector<T> &points,ld val1,ld val2){
  ld val3=sqrt(1-val1*val1-val2*val2);
  ld mx=-1e9,mn=1e9;
  
  rep(i,0,n){
    auto [x,y,z]=points[i];
    ld val=val1*x+val2*y+val3*z;
    mx=max(mx,val);
    mn=min(mn,val);
  }

  return mx-mn;
}

ld f(int n,vector<T> &points,ld val){
  ld t=1-val*val;
  
  ld low=sqrt(t),high=sqrt(t);
  low*=-1;

  rep(time,0,500){
    ld mid1 = (low * 2.0L + high) / 3.0L;
    ld mid2 = (low + high * 2.0L) / 3.0L;

    if(g(n,points,val,mid1)<g(n,points,val,mid2)){
      high=mid2;
    }
    else{
      low=mid1;
    }
  }

  return g(n,points,val,low);
}

ld solve(int n,vector<T> &points){
  ld low=-1,high=1;
  rep(time,0,500){
    ld mid1 = (low * 2.0L + high) / 3.0L;
    ld mid2 = (low + high * 2.0L) / 3.0L;

    if(f(n,points,mid1)<f(n,points,mid2)){
      high=mid2;
    }
    else{
      low=mid1;
    }
  }

  // cout<<low<<endl;
  return f(n,points,low);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;cin>>n;
  vector<T> points(n);
  
  rep(i,0,n){
    int x,y,z;cin>>x>>y>>z;
    points[i]={x,y,z};
  }

  ld ans=1e9;
  vector<T> points2(n);

  rep(i,0,6){
    rep(j,0,n){
      auto [x,y,z]=points[j];
      if(i==0)points2[j]={x,y,z};
      if(i==1)points2[j]={x,z,y};
      if(i==2)points2[j]={y,x,z};
      if(i==3)points2[j]={y,z,x};
      if(i==4)points2[j]={z,x,y};
      if(i==5)points2[j]={z,y,x};

      auto [x2,y2,z2]=points2[j];
      // cout<<x2<<" "<<y2<<" "<<z2<<endl;
    }

    ans=min(ans,solve(n,points2));
    // cout<<ans<<endl;
  }

  cout<<fixed<<setprecision(20);
  cout<<ans<<endl;
}

詳細信息

Test #1:

score: 100
Accepted
time: 214ms
memory: 3976kb

input:

8
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

output:

1.00000000000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 162ms
memory: 3812kb

input:

5
1 1 1
1 2 1
1 1 2
1 2 2
2 1 1

output:

0.70710678118654752438

result:

ok found '0.707106781', expected '0.707106781', error '0.000000000'

Test #3:

score: -100
Time Limit Exceeded

input:

50
973 1799 4431
1036 1888 4509
1099 1977 4587
1162 2066 4665
1225 2155 4743
1288 2244 4821
1351 2333 4899
1414 2422 4977
1540 2600 5133
1603 2689 5211
1666 2778 5289
1729 2867 5367
1792 2956 5445
1855 3045 5523
1918 3134 5601
1981 3223 5679
2044 3312 5757
2107 3401 5835
2170 3490 5913
2296 3668 606...

output:

0.00000000000000022204

result: