QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#802367#9869. Horizon Scanningucup-team112#AC ✓86ms9140kbC++2016.4kb2024-12-07 13:32:382024-12-07 13:32:38

Judging History

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

  • [2024-12-07 13:32:38]
  • 评测
  • 测评结果:AC
  • 用时:86ms
  • 内存:9140kb
  • [2024-12-07 13:32:38]
  • 提交

answer


//#define _GLIBCXX_DEBUG

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
using namespace std;


#ifdef LOCAL
#include <debug_print.hpp>
#define OUT(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define OUT(...) (static_cast<void>(0))
#endif

#define endl '\n'
#define lfs cout<<fixed<<setprecision(15)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)

namespace template_tute{
  using ll = long long;
  using ld = long double;
  const ll MOD1 = 1e9+7;
  const ll MOD9 = 998244353;
  const ll INF = 4.1e18;
  using P = pair<ll, ll>;
  template<typename T> using PQ = priority_queue<T>;
  template<typename T> using QP = priority_queue<T,vector<T>,greater<T>>;
  template<typename T1, typename T2>bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
  template<typename T1, typename T2>bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
  ll median(ll a,ll b, ll c){return a+b+c-max<ll>({a,b,c})-min<ll>({a,b,c});}
  void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
  void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
  void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
  template<typename T1,typename T2>void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
  template<typename T1,typename T2,typename T3>void anss(T1 x,T2 y,T3 z){ans(x!=y,x,z);};  
  template<typename T>void debug(const T &v,ll h,ll w,string sv=" "){for(ll i=0;i<h;i++){cout<<v[i][0];for(ll j=1;j<w;j++)cout<<sv<<v[i][j];cout<<endl;}};
  template<typename T>void debug(const T &v,ll n,string sv=" "){if(n!=0)cout<<v[0];for(ll i=1;i<n;i++)cout<<sv<<v[i];cout<<endl;};
  template<typename T>void debug(const vector<T>&v){debug(v,v.size());}
  template<typename T>void debug(const vector<vector<T>>&v){for(auto &vv:v)debug(vv,vv.size());}
  template<typename T>void debug(stack<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(queue<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(deque<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop_front();}cout<<endl;}
  template<typename T>void debug(PQ<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(QP<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(const set<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
  template<typename T>void debug(const multiset<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
  template<typename T,size_t size>void debug(const array<T, size> &a){for(auto z:a)cout<<z<<" ";cout<<endl;}
  template<typename T,typename V>void debug(const map<T,V>&v){for(auto z:v)cout<<"["<<z.first<<"]="<<z.second<<",";cout<<endl;}
  template<typename T>vector<vector<T>>vec(ll x, ll y, T w){vector<vector<T>>v(x,vector<T>(y,w));return v;}
  vector<ll>dx={1,-1,0,0,1,1,-1,-1};vector<ll>dy={0,0,1,-1,1,-1,1,-1};
  template<typename T>vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
  template<typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
  template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2>&p){return os << "(" << p.first << "," << p.second << ")";}
  template<typename T>ostream &operator<<(ostream &os, const vector<T> &v){os<<"[";for(auto &z:v)os << z << ",";os<<"]"; return os;}
  template<typename T>void rearrange(vector<int>&ord, vector<T>&v){
    auto tmp = v;
    for(int i=0;i<tmp.size();i++)v[i] = tmp[ord[i]];
  }
  template<typename Head, typename... Tail>void rearrange(vector<int>&ord,Head&& head, Tail&&... tail){
    rearrange(ord, head);
    rearrange(ord, tail...);
  }
  template<typename T> vector<int> ascend(const vector<T>&v){
    vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],i)<make_pair(v[j],j);});
    return ord;
  }
  template<typename T> vector<int> descend(const vector<T>&v){
    vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],-i)>make_pair(v[j],-j);});
    return ord;
  }
  template<typename T> vector<T> inv_perm(const vector<T>&ord){
    vector<T>inv(ord.size());
    for(int i=0;i<ord.size();i++)inv[ord[i]] = i;
    return inv;
  }
  ll FLOOR(ll n,ll div){assert(div>0);return n>=0?n/div:(n-div+1)/div;}
  ll CEIL(ll n,ll div){assert(div>0);return n>=0?(n+div-1)/div:n/div;}
  ll digitsum(ll n){ll ret=0;while(n){ret+=n%10;n/=10;}return ret;}
  ll modulo(ll n,ll d){return (n%d+d)%d;};
  template<typename T>T min(const vector<T>&v){return *min_element(v.begin(),v.end());}
  template<typename T>T max(const vector<T>&v){return *max_element(v.begin(),v.end());}
  template<typename T>T acc(const vector<T>&v){return accumulate(v.begin(),v.end(),T(0));};
  template<typename T>T reverse(const T &v){return T(v.rbegin(),v.rend());};
  //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  int popcount(ll x){return __builtin_popcountll(x);};
  int poplow(ll x){return __builtin_ctzll(x);};
  int pophigh(ll x){return 63 - __builtin_clzll(x);};
  template<typename T>T poll(queue<T> &q){auto ret=q.front();q.pop();return ret;};
  template<typename T>T poll(priority_queue<T> &q){auto ret=q.top();q.pop();return ret;};
  template<typename T>T poll(QP<T> &q){auto ret=q.top();q.pop();return ret;};
  template<typename T>T poll(stack<T> &s){auto ret=s.top();s.pop();return ret;};
  ll MULT(ll x,ll y){if(LLONG_MAX/x<=y)return LLONG_MAX;return x*y;}
  ll POW2(ll x, ll k){ll ret=1,mul=x;while(k){if(mul==LLONG_MAX)return LLONG_MAX;if(k&1)ret=MULT(ret,mul);mul=MULT(mul,mul);k>>=1;}return ret;}
  ll POW(ll x, ll k){ll ret=1;for(int i=0;i<k;i++){if(LLONG_MAX/x<=ret)return LLONG_MAX;ret*=x;}return ret;}
  std::ostream &operator<<(std::ostream &dest, __int128_t value) {
    std::ostream::sentry s(dest);
    if (s) {
      __uint128_t tmp = value < 0 ? -value : value;
      char buffer[128];
      char *d = std::end(buffer);
      do {
        --d;
        *d = "0123456789"[tmp % 10];
        tmp /= 10;
      } while (tmp != 0);
      if (value < 0) {
        --d;
        *d = '-';
      }
      int len = std::end(buffer) - d;
      if (dest.rdbuf()->sputn(d, len) != len) {
        dest.setstate(std::ios_base::badbit);
      }
    }
    return dest;
  }
  namespace converter{
    int dict[500];
    const string lower="abcdefghijklmnopqrstuvwxyz";
    const string upper="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string digit="0123456789";
    const string digit1="123456789";
    void regi_str(const string &t){
      for(int i=0;i<t.size();i++){
        dict[t[i]]=i;
      }
    }
    void regi_int(const string &t){
      for(int i=0;i<t.size();i++){
        dict[i]=t[i];
      }
    }
    vector<int>to_int(const string &s,const string &t){
      regi_str(t);
      vector<int>ret(s.size());
      for(int i=0;i<s.size();i++){
        ret[i]=dict[s[i]];
      }
      return ret;
    }
    vector<int>to_int(const string &s){
      auto t=s;
      sort(t.begin(),t.end());
      t.erase(unique(t.begin(),t.end()),t.end());
      return to_int(s,t);
    }
    
    vector<vector<int>>to_int(const vector<string>&s,const string &t){
      regi_str(t);
      vector<vector<int>>ret(s.size(),vector<int>(s[0].size()));
      for(int i=0;i<s.size();i++){
        for(int j=0;j<s[0].size();j++){
          ret[i][j]=dict[s[i][j]];
        }
      }
      return ret;
    }
    vector<vector<int>>to_int(const vector<string>&s){
      string t;
      for(int i=0;i<s.size();i++){
        t+=s[i];
      }
      sort(t.begin(),t.end());t.erase(unique(t.begin(),t.end()),t.end());
      return to_int(s,t);
    }
    string to_str(const vector<int>&s,const string &t){
      regi_int(t);
      string ret;
      for(auto z:s)ret+=dict[z];
      return ret;
    }
    vector<string> to_str(const vector<vector<int>>&s,const string &t){
      regi_int(t);
      vector<string>ret(s.size());
      for(int i=0;i<s.size();i++){
        for(auto z:s[i])ret[i]+=dict[z];
      }
      return ret;
    }
  }
  template< typename T = int >
  struct edge {
    int to;
    T cost;
    int id;
    edge():to(-1),id(-1){};
    edge(int to, T cost = 1, int id = -1):to(to), cost(cost), id(id){}
    operator int() const { return to; }
  };

  template<typename T>
  using Graph = vector<vector<edge<T>>>;
  template<typename T>
  Graph<T>revgraph(const Graph<T> &g){
    Graph<T>ret(g.size());
    for(int i=0;i<g.size();i++){
      for(auto e:g[i]){
        int to = e.to;
        e.to = i;
        ret[to].push_back(e);
      }
    }
    return ret;
  }
  template<typename T>
  Graph<T> readGraph(int n,int m,int indexed=1,bool directed=false,bool weighted=false){
    Graph<T> ret(n);
    for(int es = 0; es < m; es++){
      int u,v;
      T w=1;
      cin>>u>>v;u-=indexed,v-=indexed;
      if(weighted)cin>>w;
      ret[u].emplace_back(v,w,es);
      if(!directed)ret[v].emplace_back(u,w,es);
    }
    return ret;
  }
  template<typename T>
  Graph<T> readParent(int n,int indexed=1,bool directed=true){
    Graph<T>ret(n);
    for(int i=1;i<n;i++){
      int p;cin>>p;
      p-=indexed;
      ret[p].emplace_back(i);
      if(!directed)ret[i].emplace_back(p);
    }
    return ret;
  }
}
using namespace template_tute;

using I = long long;
struct Point{
  I x, y;
  Point(): x(0), y(0){}
  Point(I x,I y):x(x),y(y){}
  Point &operator+=(const Point &p){
    x += p.x, y += p.y;
    return *this;
  }
  Point &operator-=(const Point &p){
    x -= p.x, y -= p.y;
    return *this;
  }
  Point &operator*=(I v){
    x *= v, y *= v;
    return *this;
  }
  Point &operator/=(I v){
    assert(x % v == 0 && y % v == 0);
    x /= v, y /= v;
    return *this;
  }
  friend Point operator+(const Point &l, const Point &r){
    return Point(l) += r;
  }
  friend Point operator-(const Point &l, const Point &r){
    return Point(l) -= r;
  }
  friend Point operator*(const Point &l, I r){
    return Point(l) *= r;
  }
  friend Point operator/(const Point &l, I r){
    return Point(l) /= r;
  }
  bool operator<(const Point &p)const{
    if(x == p.x)return y < p.y;
    return x < p.x;
  }
  bool operator>(const Point &p) const{
    if(x == p.x)return y > p.y;
    return x > p.x;
  }
  bool operator==(const Point &p)const{return x == p.x && y == p.y;}
  bool operator!=(const Point &p)const{return x != p.x || y != p.y;}
  friend ostream &operator<<(ostream &os, const Point &p) {
    return os << "(" << p.x << "," << p.y << ")";
  }
  friend istream &operator>>(istream &is, Point &p) {
    is >> p.x >> p.y;
    return (is);
  }

};

struct Line{
  Point a,b;
  Line() = default;
  Line(Point a, Point b) : a(a), b(b){}
};

I norm(const Point &p){
  return p.x * p.x + p.y * p.y;
}

I dot(const Point &a, const Point &b){
  return a.x * b.x + a.y * b.y;
}

I cross(const Point &a, const Point &b){
  return a.x * b.y - a.y * b.x;
}

I distance(const Point &a, const Point &b){
  return norm(a - b);
}
I area(const Point &a,const Point &b,const Point &c){
  return abs(cross(b-a,c-a));
}
constexpr int COUNTER_CLOCKWISE = +1;
constexpr int CLOCKWISE = -1;
constexpr int ONLINE_BACK = +2; // c-a-b
constexpr int ONLINE_FRONT = -2; // a-b-c
constexpr int ON_SEGMENT = 0; // a-c-b

int ccw(const Point &a, Point b, Point c) {
  b = b - a, c = c - a;
  if(cross(b, c) > 0) return COUNTER_CLOCKWISE;
  if(cross(b, c) < 0) return CLOCKWISE;
  if(dot(b, c) < 0) return ONLINE_BACK;
  if(norm(b) < norm(c)) return ONLINE_FRONT;
  return ON_SEGMENT;
}

bool parallel(const Line &a, const Line &b){
  return cross(a.b - a.a, b.b - b.a) == 0;
}

bool orthogonal(const Line &a, const Line &b){
  return dot(a.a - a.b, b.a - b.b) == 0;
}

bool argument_compare(Point a, Point b){
  if(a.x == 0 && a.y == 0)a.x = 1;
  if(b.x == 0 && b.y == 0)b.x = 1;
  if(a.y < 0 && b.y >= 0){
    return true;
  }
  else if(a.y >= 0 && b.y < 0){
    return false;
  }
  else if(a.y == 0 && b.y == 0){
    return a.x >= 0 && b.x < 0;
  }
  return cross(a, b) > 0;
}

vector<Point>convex_hull(const vector<Point>&points, bool onEdge = false){
  int n = points.size(), k = 0;
  auto p = points;
  const I limit = onEdge ? 0 : 1;
  if(n <= 2)return p;
  sort(p.begin(), p.end());
  vector<Point> ch(2 * n);
  for(int i = 0; i < n; ch[k++] = p[i++]) {
    while(k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < limit) --k;
  }
  for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {
    while(k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < limit) --k;
  }
  ch.resize(k - 1);
  return ch;
}
vector<Point>lower_convex_hull(const vector<Point>&points, bool onEdge = false){
  int n = points.size(), k = 0;
  auto p = points;
  const I limit = onEdge ? 0 : 1;
  if(n <= 2)return p;
  sort(p.begin(), p.end());
  vector<Point> ch(2 * n);
  for(int i = 0; i < n; ch[k++] = p[i++]) {
    while(k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < limit) --k;
  }
  ch.resize(k);
  return ch;
}
//各b_jに対して、cross(a_i,b_j)の最大値を求める
vector<I>get_cross_max(vector<Point>a,vector<Point>b){
  a = convex_hull(a, false);
  vector<int>ord(b.size());
  iota(ord.begin(),ord.end(),0);
  sort(ord.begin(),ord.end(),[&](int i,int j){return argument_compare(b[i],b[j]);});
  vector<I>ret(b.size());
  if(norm(b[ord[0]]) == 0 && norm(b[ord.back()]) == 0){
    return ret;
  }
  int start = 0;
  while(norm(b[ord[start]]) == 0)start++;
  int max_arg = 0;
  for(int i = 1; i < a.size(); i++){
    if(cross(a[max_arg], b[ord[start]]) < cross(a[i], b[ord[start]])){
      max_arg = i;
    }
  }
  for(auto i:ord){
    while(1){
      I c0 = cross(a[(max_arg == 0 ? a.size() - 1 : max_arg - 1)],b[i]);
      I c1 = cross(a[max_arg],b[i]);
      I c2 = cross(a[(max_arg == a.size() - 1 ? 0 : max_arg + 1)],b[i]);
      if(c0 <= c1 && c1 >= c2)break;
      max_arg++;
      if(max_arg >= a.size())max_arg -= a.size();
    }
    ret[i] = cross(a[max_arg], b[i]);
  }
  return ret;
}
vector<I>get_cross_min(vector<Point>a,vector<Point>b){
  for(auto &p:b)p *= -1;
  auto ret = get_cross_max(a, b);
  for(auto &r:ret)r *= -1;
  return ret;
}
vector<I>get_dot_max(vector<Point>a,vector<Point>b){
  for(auto &p:b){
    p = Point(-p.y, p.x);
  }
  auto ret=get_cross_max(a,b);
  return ret;
}
// 多角形と点の包含判定
enum {
  OUT, ON, IN
};
using Polygon=vector<Point>;
int contains(const Polygon &Q, const Point &p) {
  bool in = false;
  for(int i = 0; i < Q.size(); i++) {
    Point a = Q[i] - p, b = Q[(i + 1) % Q.size()] - p;
    if(a.y > b.y) swap(a, b);
    if(a.y <= 0 && 0 < b.y && cross(a, b) < 0) in = !in;
    if(cross(a, b) == 0 && dot(a, b) <= 0) return ON;
  }
  return in ? IN : OUT;
}

bool segment_intersect(const Line &s, const Line &t) {
  return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 && ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

bool segment_point_intersect(const Line &s, const Point &p) {
  return ccw(s.a, s.b, p) == 0;
}

void solve(){
	ll res=0,buf=0;
  bool judge = true;

  ll n,k;cin>>n>>k;
  vector<Point>p(n); 
  rep(i,0,n)cin>>p[i];
  ld pi=acos(-1);
  vector<ld>at(n);
  rep(i,0,n){
    at[i]=atan2<ld>(p[i].y,p[i].x);
  }
  if(n==k||abs(max(at)-min(at))<1e-10){
    cout<<2*pi<<endl;
    return;
  }
  sort(ALL(p),argument_compare);
  ld ret=0;
  k=n-k;
  rep(i,0,n){
    
    auto l=p[i],r=p[(i+k)%n],pre=p[(i-1+n)%n];
    auto lc=atan2<ld>(l.y,l.x),rc=atan2<ld>(r.y,r.x);
    auto prec=atan2<ld>(pre.y,pre.x);
    if(abs(prec-lc)<1e-10)continue;
    //OUT(lc,rc,lc>rc);
    if(lc>rc)rc+=2*pi;
    chmax(ret,2*pi-(rc-lc));
  }
  cout<<ret<<endl;
}

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  int T = 1;
  cin>>T;
  lfs;
  while(T--){
    solve();
  }
  return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3924kb

input:

5
1 1
0 1
8 2
1 0
1 1
0 1
-1 1
-1 0
-1 -1
0 -1
1 -1
4 2
-1 1
0 1
0 2
1 1
4 2
-1000000000 0
-998244353 1
998244353 1
1000000000 0
3 1
0 1
0 2
0 -1

output:

6.283185307179586
1.570796326794897
5.497787143782138
3.141592654591552
3.141592653589793

result:

ok 5 numbers

Test #2:

score: 0
Accepted
time: 50ms
memory: 3964kb

input:

10000
16 1
-10 -6
-5 -6
-4 9
-2 5
-2 10
1 -7
1 -5
1 6
3 1
4 -9
6 -10
6 -3
6 1
8 -5
8 -4
9 -4
17 4
-9 2
-8 -4
-8 -3
-8 -1
-6 -2
-6 -1
-6 8
-5 -8
-5 10
-4 8
-2 -8
4 -9
4 0
5 -3
8 -5
9 -2
10 10
10 6
-7 2
-4 6
-2 -7
-2 -1
-1 7
1 -9
1 8
3 -4
7 -4
9 -2
14 3
-9 10
-8 -10
-8 -8
-6 -7
-6 -5
-1 -7
-1 -2
0 -1
...

output:

1.692991497486251
2.574863436066287
4.652758267253520
2.772633107383937
5.742765806909002
4.857698991020392
3.419892312594904
2.812799962084839
6.283185307179586
6.283185307179586
5.117280766669773
6.146782702778639
3.842089023537519
2.342496716819479
3.463343207986435
6.283185307179586
5.9614347527...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 50ms
memory: 3940kb

input:

10000
19 7
-10 -6
-10 5
-3 0
-2 -5
-1 1
-1 6
0 3
0 7
1 9
3 -3
3 3
3 8
4 -1
5 8
6 -3
7 -5
7 4
8 10
9 -5
15 15
-9 -1
-8 6
-7 9
-6 -3
-4 -9
-1 -3
-1 8
1 -8
1 -7
3 -2
3 1
6 -9
7 -10
7 0
10 -9
10 3
-7 -1
-6 -2
-6 10
-5 2
-4 2
-3 -7
-2 -9
1 -3
3 4
7 7
15 4
-8 -8
-8 8
-7 0
-7 10
-6 -7
-5 6
-1 -3
-1 0
1 -2
...

output:

3.926990816987241
6.283185307179586
3.360261599463735
2.677945044588987
3.770388940005226
1.762584468781602
3.840252478311256
5.497787143782138
2.034443935795703
1.815774989921761
4.347187530596517
6.141288252575422
5.176036589385496
5.465540261346884
5.769039151267022
4.366253016815329
5.9947557486...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 49ms
memory: 3820kb

input:

10000
18 12
-10 -4
-10 7
-8 -10
-7 -4
-6 5
-6 7
-5 0
-2 -7
-1 2
-1 10
0 2
1 1
3 -2
5 3
5 5
6 -3
8 -3
9 -2
10 1
-10 -9
-7 -7
-5 2
-4 -7
-3 1
3 1
3 3
5 -4
9 2
9 6
11 2
-8 1
-8 6
-7 -2
-6 0
-5 0
-1 -9
2 -8
3 5
6 0
10 -2
10 6
20 9
-10 -6
-10 6
-9 -8
-7 5
-6 -4
-4 -8
-2 -10
-2 -3
-2 4
-1 1
2 -5
3 -2
5 -6...

output:

4.909784540234570
1.975688113079980
1.986860832518719
3.926990816987241
3.697758883710246
6.283185307179586
6.141288252575422
6.193871314186364
5.805354252187471
6.252891547260811
5.728877810978035
3.090091842638568
1.892546881191539
5.634189748183085
2.896613990462929
6.283185307179586
2.9147938055...

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 45ms
memory: 3900kb

input:

10000
19 7
-10 -1
-8 2
-7 -10
-6 6
-4 7
-3 -5
-3 1
-3 8
-2 4
-1 -7
0 -8
0 9
1 -10
2 1
2 3
3 5
6 -4
10 2
10 3
14 10
-8 2
-6 0
-5 -10
-5 10
-4 7
-3 -6
-2 -6
1 4
1 6
2 -1
3 -6
8 -4
9 -10
10 -1
12 8
-9 5
-7 2
-4 2
0 -2
0 5
1 6
3 2
4 9
5 5
7 -6
9 -9
9 2
19 12
-10 -10
-10 2
-9 -6
-8 2
-7 -5
-6 8
-4 1
-1 -...

output:

3.239319560948512
5.275705241876658
5.300391583932257
5.387129922608242
5.888394187479825
4.117319356679148
1.138388551224359
1.515297821549180
6.147657593194085
6.158830312632825
2.574863436066287
5.940161366758883
1.608514279261761
4.609945126877565
5.071159650655262
4.234557925392575
3.7905882125...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 50ms
memory: 3872kb

input:

10000
11 10
-10 -1
-9 4
-9 10
-7 -7
-5 4
-4 -1
-2 -10
0 -7
0 5
3 3
3 5
12 12
-9 6
-9 8
-3 -2
-2 2
0 -4
1 0
2 -3
3 5
5 -2
7 -1
10 3
10 9
14 12
-10 0
-9 -3
-9 1
-9 10
-8 -1
-8 7
-6 -1
-1 -6
-1 2
1 -1
3 -7
4 9
9 -3
10 1
10 4
-9 -3
-7 -1
-6 -10
-3 -2
-3 7
2 -2
2 3
5 2
6 9
9 6
10 2
-9 -9
-9 6
-8 3
-5 -9
...

output:

6.137875296543884
6.283185307179586
6.118036629764960
3.200348476305516
2.653756214930151
6.253782018975581
3.605240262590599
3.559816983169022
1.509146156155638
5.927549422878826
6.258799898006868
2.622446539343270
4.393833303296623
5.497787143782138
4.248741371383883
5.497787143782138
4.6292477484...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 50ms
memory: 3952kb

input:

10000
14 1
-100 13
-96 -31
-82 -92
-77 -98
-50 1
-14 -57
-14 -31
-11 64
-8 75
9 68
25 100
54 -36
59 13
93 31
19 19
-76 -39
-60 95
-51 18
-39 11
-21 -46
-6 -94
-5 83
-3 -34
-3 72
0 -55
3 79
14 17
23 -88
32 37
50 70
61 -5
62 -43
84 -100
97 -50
13 7
-99 -63
-68 -87
-24 62
-20 -18
-2 -66
7 -49
13 -21
15...

output:

1.271309397461279
6.283185307179586
5.222514720736499
6.003065703568917
3.925872135464679
5.546528995092070
3.210314923711723
3.039930049923723
4.227531781794426
3.032019665736877
2.191215233818190
3.039008090367741
4.331327150635503
6.283185307179586
5.110002265051219
2.946314026061502
5.1760365893...

result:

ok 10000 numbers

Test #8:

score: 0
Accepted
time: 51ms
memory: 3904kb

input:

100
1413 755
-30 -30
-30 -28
-30 -27
-30 -26
-30 -21
-30 -12
-30 -10
-30 -8
-30 -5
-30 -1
-30 2
-30 4
-30 7
-30 9
-30 17
-30 19
-30 20
-30 23
-30 24
-30 30
-29 -29
-29 -23
-29 -15
-29 0
-29 4
-29 5
-29 9
-29 10
-29 11
-29 12
-29 14
-29 16
-29 17
-29 22
-29 27
-29 28
-28 -28
-28 -25
-28 -23
-28 -22
-...

output:

3.589112628746963
2.979755222351370
0.283794109208328
2.035027706891093
4.887981142334870
1.004067109271390
4.745709976262937
5.325596329259199
4.310274964732927
5.603383679413830
1.579805092085314
4.329645470539114
5.547222096794092
1.460139105621001
1.531044551399049
2.871674931708135
2.6325789668...

result:

ok 100 numbers

Test #9:

score: 0
Accepted
time: 54ms
memory: 4188kb

input:

20
9045 8319
-1000 -986
-1000 -683
-1000 -430
-1000 -292
-1000 53
-1000 667
-999 -855
-999 -350
-999 -174
-999 -51
-999 -43
-999 235
-999 465
-999 530
-998 -997
-998 -311
-998 21
-998 44
-998 182
-997 -313
-997 -195
-997 -13
-997 412
-997 425
-996 -542
-996 -348
-996 -126
-996 -59
-996 -40
-996 84
-...

output:

5.911511003904026
3.743868515137712
2.538482858315347
2.159967358857887
4.295037709572344
4.771674474796183
4.682407812601936
5.078984394174574
1.600801821410664
3.340402545636705
3.368792528250349
2.113016028230062
4.855399410132670
4.324001053270539
0.107853561070644
0.179821124177803
5.3766547606...

result:

ok 20 numbers

Test #10:

score: 0
Accepted
time: 66ms
memory: 8444kb

input:

1
166347 18723
-1000 -979
-1000 -975
-1000 -928
-1000 -914
-1000 -898
-1000 -889
-1000 -876
-1000 -873
-1000 -858
-1000 -840
-1000 -838
-1000 -801
-1000 -783
-1000 -744
-1000 -738
-1000 -733
-1000 -713
-1000 -712
-1000 -695
-1000 -689
-1000 -680
-1000 -675
-1000 -671
-1000 -646
-1000 -643
-1000 -608...

output:

0.851449178980516

result:

ok found '0.8514492', expected '0.8514492', error '0.0000000'

Test #11:

score: 0
Accepted
time: 60ms
memory: 8036kb

input:

1
154903 84960
-1000 -979
-1000 -965
-1000 -956
-1000 -945
-1000 -920
-1000 -901
-1000 -878
-1000 -860
-1000 -858
-1000 -709
-1000 -693
-1000 -648
-1000 -619
-1000 -602
-1000 -579
-1000 -474
-1000 -473
-1000 -454
-1000 -443
-1000 -427
-1000 -407
-1000 -403
-1000 -384
-1000 -351
-1000 -279
-1000 -244...

output:

3.538926685383166

result:

ok found '3.5389267', expected '3.5389267', error '0.0000000'

Test #12:

score: 0
Accepted
time: 62ms
memory: 8248kb

input:

1
158037 96343
-1000 -1000
-1000 -905
-1000 -881
-1000 -833
-1000 -804
-1000 -803
-1000 -782
-1000 -775
-1000 -765
-1000 -759
-1000 -756
-1000 -748
-1000 -722
-1000 -674
-1000 -669
-1000 -630
-1000 -610
-1000 -573
-1000 -443
-1000 -411
-1000 -409
-1000 -403
-1000 -388
-1000 -366
-1000 -349
-1000 -33...

output:

3.972028778325881

result:

ok found '3.9720288', expected '3.9720288', error '0.0000000'

Test #13:

score: 0
Accepted
time: 60ms
memory: 4036kb

input:

10000
17 12
-853202371 684059854
-659446544 -924219854
-418025687 117998679
-399757126 -365708913
-331597239 -270896799
-204989763 869548983
-118492298 963842298
-77481232 672198731
45930201 -58234380
52605147 -900097542
78371985 940503934
235210685 595759114
391284089 234315077
416229789 -827244230...

output:

5.398525110034352
5.373907874856423
1.173578172874162
1.544365259508386
3.778288649403068
3.570471586852505
6.282974858836159
5.095925202815100
2.987578246550850
2.305566505801529
3.390784164182035
5.785473238128133
4.810963612263964
0.956757418042080
4.629431730977267
4.799508062883596
4.1702889055...

result:

ok 10000 numbers

Test #14:

score: 0
Accepted
time: 56ms
memory: 3972kb

input:

1000
133 108
-994106086 710243426
-991027749 -548437545
-983318226 -917527783
-943673956 -368162275
-935819096 616077188
-928022346 487569673
-924213856 -369318351
-914827619 426646545
-883935180 590882141
-870015071 -270471333
-834927107 -211343853
-829266515 354007200
-788041913 -60481736
-7822837...

output:

5.742801792143195
1.915364239841794
3.804345798108007
1.791916270531130
3.169520670635203
6.078646214615602
3.786067459510641
3.665969072687856
6.226583452970446
5.902152192610390
5.944315709295676
0.715167687043102
3.831574252977200
1.222845718460307
2.598426466949443
5.547328920507700
4.0791947427...

result:

ok 1000 numbers

Test #15:

score: 0
Accepted
time: 63ms
memory: 3904kb

input:

100
1367 924
-999416811 990355566
-997656126 346133696
-997071616 -657387469
-996176051 12622726
-995720693 334093112
-995478093 891631278
-994503890 341858449
-994297596 499383911
-993234202 533518057
-991636838 -4170504
-990563582 -407186200
-989454027 653116272
-989132124 -780605454
-988073521 -1...

output:

4.505153490617689
2.712558932627478
5.839678580981967
6.022977111452615
0.461606043101416
0.986991233212523
1.321970848834323
1.925841745838059
5.508608353349911
4.646355331297879
2.287677410207707
2.184872587796329
4.809409191806839
0.477078990241138
0.556341605008780
1.093619164153342
5.1827145536...

result:

ok 100 numbers

Test #16:

score: 0
Accepted
time: 63ms
memory: 4436kb

input:

10
13806 4955
-999669776 933068103
-999542354 721337508
-999499427 357140594
-999429088 -925180511
-999334813 -145726169
-999291694 -886327684
-999281647 811188099
-999145269 860687107
-998961821 -979442436
-998769313 446186367
-998591455 658309173
-998539751 -569480843
-998479467 279850955
-9984754...

output:

2.417080468033978
6.161192229078727
3.960020376842235
3.994361792904593
2.551550836155520
0.522723836780999
4.097843827854229
6.210382663158929
5.981728029253966
0.777223685890601

result:

ok 10 numbers

Test #17:

score: 0
Accepted
time: 48ms
memory: 6728kb

input:

1
112596 94970
-999980219 399324466
-999932413 952114487
-999894556 -951211102
-999891030 -996222974
-999864824 412806264
-999853190 -269700371
-999845814 -23906803
-999841507 -459154880
-999825178 716247149
-999761774 -154047106
-999729655 -171480333
-999709604 -666447277
-999704754 -22442485
-9996...

output:

5.442593879343852

result:

ok found '5.4425939', expected '5.4425939', error '0.0000000'

Test #18:

score: 0
Accepted
time: 75ms
memory: 8292kb

input:

1
161568 13252
-999991243 -113889211
-999976572 -361096764
-999970140 -505012445
-999960654 600963873
-999959339 -269932510
-999956568 734634576
-999941447 716485764
-999940305 64397798
-999939982 746532931
-999939921 995002380
-999932747 185078659
-999927136 585216518
-999914684 898656539
-99990452...

output:

0.642474590686497

result:

ok found '0.6424746', expected '0.6424746', error '0.0000000'

Test #19:

score: 0
Accepted
time: 86ms
memory: 9140kb

input:

1
186192 126483
-999998234 974001047
-999976292 -133179660
-999967957 112862981
-999957851 70030467
-999951528 743907713
-999931316 66002112
-999907988 888991267
-999905412 470798211
-999903986 -103943462
-999900422 255729004
-999898174 917068198
-999884392 -183592605
-999880179 -650076162
-99987469...

output:

4.401245684119010

result:

ok found '4.4012457', expected '4.4012457', error '0.0000000'

Test #20:

score: 0
Accepted
time: 55ms
memory: 3896kb

input:

1000
133 9
-10 -839744900
-10 -620593257
-10 -322048342
-10 578093727
-10 898998949
-9 -833794004
-9 -704882916
-9 -570204575
-9 -506146571
-9 -109555290
-9 309734100
-9 396668416
-8 -928874025
-8 376566668
-8 596463598
-8 600491164
-8 894775141
-7 -281322833
-7 49984651
-7 154512939
-7 205573228
-7...

output:

3.141592582887780
6.283185248213678
3.141592614424978
3.141591174081442
6.283185270291753
6.283185295316328
3.141592649229425
6.283185303670099
3.141592640161558
6.283185250675928
6.283185281648257
3.141592759186940
3.141592645370557
3.141592623755958
3.141592615211536
6.283185273315125
3.1415926493...

result:

ok 1000 numbers

Test #21:

score: 0
Accepted
time: 54ms
memory: 4824kb

input:

5
23120 8224
-10 -999575056
-10 -997485895
-10 -995458183
-10 -986953157
-10 -985268102
-10 -983223383
-10 -980910524
-10 -980404283
-10 -973605147
-10 -972441960
-10 -972440422
-10 -969122114
-10 -965754004
-10 -964812113
-10 -964558462
-10 -963159275
-10 -962972564
-10 -962085557
-10 -961552443
-1...

output:

3.141592642351389
3.141592618624913
3.141592606433533
3.141592649395319
6.283185271717992

result:

ok 5 numbers

Test #22:

score: 0
Accepted
time: 36ms
memory: 6252kb

input:

1
99995 60000
1 100001
1 100002
1 100003
1 100004
1 100005
1 100006
1 100007
1 100008
1 100009
1 100010
1 100011
1 100012
1 100013
1 100014
1 100015
1 100016
1 100017
1 100018
1 100019
1 100020
1 100021
1 100022
1 100023
1 100024
1 100025
1 100026
1 100027
1 100028
1 100029
1 100030
1 100031
1 10003...

output:

6.283183640474032

result:

ok found '6.2831836', expected '6.2831853', error '0.0000003'

Extra Test:

score: 0
Extra Test Passed