QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88600#5505. Great ChaseJerryBlack#WA 422ms3672kbC++179.7kb2023-03-16 18:32:352023-03-16 18:32:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-16 18:32:36]
  • 评测
  • 测评结果:WA
  • 用时:422ms
  • 内存:3672kb
  • [2023-03-16 18:32:35]
  • 提交

answer

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

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast,unroll-loops")

#define DECIMAL 6
namespace fastIO
{
#ifdef LOCAL
#define DEBUG
#endif
#define BUF_SIZE 100000
#define LL long long
    static bool IOerror=false;
#ifdef DEBUG
    inline char nc(){char ch=getchar();if(ch==-1)IOerror=1;return ch;}
#else
    inline char nc(){static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;if(p1==pend){p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);if(pend==p1){IOerror=true;return -1;}}return *p1++;}
#endif
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    template<class T> inline bool read(T&x){bool sign=false;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return false;if(ch=='-')sign=true,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;return true;}
    inline bool read(unsigned long long&x){char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return false;for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';return true;}
    inline bool read(unsigned int&x){char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return false;for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';return true;}
    inline bool read(double&x){bool sign=false;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return false;if(ch=='-')sign=true,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(ch=='.'){double tmp=1;ch=nc();for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');}if(sign)x=-x;return true;}
    inline bool read(char*s){char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return false;for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;*s=0;return true;}
    inline bool read(char&c){for(c=nc();blank(c);c=nc());if(IOerror){c=-1;return false;}return true;}
    inline bool read(std::string&s){s.clear();char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return false;for(;!blank(ch)&&!IOerror;ch=nc())s+=ch;return true;}
    template<class T,class... U> bool read(T&h,U&... t){return read(h)&&read(t...);}
    struct Ostream_fwrite
    {
#ifdef DEBUG
        inline void out(char ch) { putchar(ch); }
#else
        char*buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        inline void out(char ch){if(p1==pend){fwrite(buf,1,BUF_SIZE,stdout);p1=buf;}*p1++=ch;}
#endif
        template<class T> inline void print(T x){static char s[41],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void print(char ch){out(ch);}
        inline void print(unsigned long long x){static char s[41],*s1;s1=s;if(!x)*s1++='0';while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void print(unsigned int x){static char s[41],*s1;s1=s;if(!x)*s1++='0';while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void print(double x,int y=DECIMAL){static LL mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};if(x<-1e-12)out('-'),x=-x;x*=mul[y];LL x1=(LL)floor(x);if(x-floor(x)>=0.5)++x1;LL x2=x1/mul[y],x3=x1-x2*mul[y];print(x2);if(y>0){out('.');for(size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i);print(x3);}}
        inline void print(char*s){while(*s)out(*s++);}
        inline void print(const char*s){while(*s)out(*s++);}
        inline void print(std::string s){print(s.c_str());}
#ifndef DEBUG
        inline void flush(){if(p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
#endif // !DEBUG
    }Ostream;
    template<class T> inline void print(T x){Ostream.print(x);}
    template<class T> inline void println(T x){Ostream.print(x);Ostream.out('\n');}
    inline void print(double x,int y=DECIMAL){Ostream.print(x,y);}
    inline void println(double x,int y=DECIMAL){Ostream.print(x,y);Ostream.out('\n');}
    template<class T,class... U> void print(const T&h,const U&... t){print(h);Ostream.out(' ');print(t...);}
    template<class T,class... U> void println(const T&h,const U&... t){print(h);Ostream.out(' ');println(t...);}
#ifndef DEBUG
    inline void flush(){Ostream.flush();}
#endif
#undef LL
#undef DECIMAL
#undef BUF_SIZE
    //本地 getchar/putchar ,提交 fread/fwrite
    //本地支持终端交互输入输出
}
using namespace fastIO;

#define ll long long
#define ull unsigned ll
#define fi first
#define se second
const double eps=1e-9;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
mt19937 rnd(time(0));

int P=1e9+9;
namespace modint
{
    int norm(int x){if(x<0)x+=P;if(x>=P)x-=P;return x;}
    template<class T>
    T power(T a,ll n){T ans=1;while(n){if(n&1)ans=ans*a;a=a*a;n>>=1;}return ans;}
    struct Z
    {
        int x;
        Z(int x=0):x(norm(x)){}
        Z(ll x):x(norm(x%P)){}
        int val() const{return x;}
        Z operator-() const{return Z(norm(P-x));}
        Z inv() const{assert(x!=0);return power(*this,P-2);}
        Z&operator*=(const Z&rhs){x=(ll)x*rhs.x%P;return *this;}
        Z&operator+=(const Z&rhs){x=norm(x+rhs.x);return *this;}
        Z&operator-=(const Z&rhs){x=norm(x-rhs.x);return *this;}
        Z&operator/=(const Z&rhs){return *this*=rhs.inv();}
        friend Z operator*(const Z&lhs,const Z&rhs){Z res=lhs;res*=rhs;return res;}
        friend Z operator+(const Z&lhs,const Z&rhs){Z res=lhs;res+=rhs;return res;}
        friend Z operator-(const Z&lhs,const Z&rhs){Z res=lhs;res-=rhs;return res;}
        friend Z operator/(const Z&lhs,const Z&rhs){Z res=lhs;res/=rhs;return res;}
        friend istream&operator>>(istream&is,Z&a){ll v;is>>v;a=Z(v);return is;}
        friend ostream&operator<<(ostream&os,const Z&a){return os<<a.val();}
    };
}
using namespace modint;

#define int ll

int dcmp(double a,double b)
{
    if(fabs(a-b)<eps)return 0;
    if(a>b)return 1;
    return -1;
}

void solve()
{
    int n,v;
    cin>>n>>v;
    vector<pair<int,int>>a,b;
    for(int i=1;i<=n;i++)
    {
        int d,V;
        cin>>d>>V;
        if(d<0)a.push_back({d,V});
        else b.push_back({d,V});
    }
    double l=0,r=2e12;
    while(dcmp(l,r)!=0)
    {
        double mid=(l+r)/2;
        double ma=-1e18,mi=1e18;
        for(auto it:a)
        {
            ma=max(ma,mid*it.second+it.first);
        }
        for(auto it:b)
        {
            mi=min(mi,-mid*it.second+it.first);
        }
        if(dcmp(ma,mi)<0)l=mid;
        else if(dcmp(ma,mi)==0)break;
        else r=mid;
    }
    if(dcmp(l,r)!=0)l=(l+r)/2;
    cout<<l*v<<'\n';
}



#undef int

int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cout<<fixed<<setprecision(15);

	int _;cin>>_;while(_--)
    {
        solve();
    }
    return 0;
}
/* ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
 * │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S/L│P/B│ │Cal│   │   │   │
 * └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘ └───┴───┴───┴───┘
 * ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
 * │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
 * ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
 * │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
 * ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
 * │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│  Enter │               │ 4 │ 5 │ 6 │   │
 * ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
 * │  Shift │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│   Shift  │     │ ↑ │     │ 1 │ 2 │ 3 │   │
 * ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
 * │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│ Fn │Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
 * └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3660kb

input:

3
4 9
10 2
-7 2
-6 1
7 1
2 8
-1 7
1 6
2 3
-1000000000000 1
1000000000000 1

output:

38.249999999626475
1.230769230021328
3000000000000.000000000000000

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 422ms
memory: 3672kb

input:

10000
200 997007
405524182320 754760
686939601648 419804
687047488212 715566
1446157132 4594
-670522037 4673
763634629282 253755
424307411732 275041
1582708381 8473
-667425982 4622
-522841486 1427
702430907988 460271
1405423646 1060
1497754648 6227
883363410675 723547
56899800372 46435
-810216390 64...

output:

145405766328.348876953125000
16414958969.727176666259766
5202715639.835095405578613
321977234.156127154827118
45384199210.221130371093750
183885744.769229531288147
1708925225.229853153228760
89786664971.557907104492188
13924365606.287366867065430
412975327.555464029312134
965508404.511801958084106
4...

result:

wrong answer 4566th numbers differ - expected: '1.0000010', found: '0.9994989', error = '0.0005021'