QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#822163#9804. Guess the Polygonucup-team3548TL 0ms3728kbC++203.0kb2024-12-19 22:54:032024-12-19 22:54:04

Judging History

This is the latest submission verdict.

  • [2024-12-19 22:54:04]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 3728kb
  • [2024-12-19 22:54:03]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
#define lll __int128
#define lf double
using namespace std;
ll Read()
{
    ll Output=0;
    char Input=getchar();
    while(Input<'0'||Input>'9')
    Input=getchar();
    while(Input>='0'&&Input<='9')
    {
        Output=Output*10+Input-'0';
        Input=getchar();
    }
    return Output;
}
void Write(lll X)
{
    if(X<0)putchar('-'),X=-X;
    if(X>9)
    Write(X/10);
    putchar('0'+X%10);
}
lll GCD(lll X,lll Y)
{
    return (Y?GCD(Y,X%Y):X);
}
struct frac
{
    lll X,Y;
    frac(lll A,lll B):X(A),Y(B)
    {
        if(A<0)
        {
            X=-X,Y=-Y;
        }
    }
    frac():frac(0,1){}
    frac(lll A):frac{A,1}{}
    explicit operator double() const
    {
        return 1.*X/Y;
    }
    void Out()
    {
        Write(X);
        putchar(' ');
        Write(Y);
    }
    void Simp()
    {
        lll Gcd=GCD(X,Y);
        X/=Gcd,Y/=Gcd;
    }
    frac operator -()const
    {
        return frac(X,-Y);
    }
    frac &operator += (const frac &Rhs)
    {
        X=X*Rhs.Y+Rhs.X*Y;
        Y*=Rhs.Y;
        Simp();
        return *this;
    }
    frac &operator -= (const frac &Rhs)
    {
        X=X*Rhs.Y+Rhs.X*Y;
        Y*=Rhs.Y;
        Simp();
        return *this;
    }
    frac &operator *= (const frac &Rhs)
    {
        X*=Rhs.X;
        Y*=Rhs.Y;
        Simp();
        return *this;
    }
    frac &operator /= (const frac &Rhs)
    {
        X*=Rhs.Y;
        Y*=Rhs.X;
        Simp();
        return *this;
    }
    friend frac operator + (const frac Lhs,const frac &Rhs)
    {
        frac Res=Lhs;
        Res+=Rhs;
        return Res;
    }
    friend frac operator - (const frac Lhs,const frac &Rhs)
    {
        frac Res=Lhs;
        Res-=Rhs;
        return Res;
    }
    friend frac operator * (const frac Lhs,const frac &Rhs)
    {
        frac Res=Lhs;
        Res*=Rhs;
        return Res;
    }
    friend frac operator / (const frac Lhs,const frac &Rhs)
    {
        frac Res=Lhs;
        Res/=Rhs;
        return Res;
    }
};
int T;
int N;
struct point
{
    int X,Y;
}Point[1001];
int Copy[1001];
bool Cmp(point A,point B)
{
    return A.X<B.X;
}
void Oper(frac X)
{
    printf("? ");
    X.Out();
    putchar('\n');
    fflush(stdout);
}
void Solve()
{
    N=Read();
    for(int i=1;i<=N;++i)
    Point[i].X=Read(),Point[i].Y=Read(),Copy[i]=Point[i].X;
    sort(Point+1,Point+N+1,Cmp);
    sort(Copy+1,Copy+N+1);
    int Len=unique(Copy+1,Copy+N+1)-Copy-1;
    frac Ans=frac();
    frac ToEnd=frac();
    for(int i=1;i<Len-(Len==N);++i)
    {
        Oper((frac(Copy[i])+frac(Copy[i+1]))/frac(2));
        int X=Read(),Y=Read();
        Ans+=frac(X,Y)*frac(Copy[i+1]-Copy[i]);
        if(Len==N)
        ToEnd=frac(X,Y)*frac(2)-ToEnd;
    }
    if(Len==N)
    Ans+=ToEnd*(frac(Copy[N]-Copy[N-1],2));
    printf("! ");
    Ans.Out();
    putchar('\n');
    fflush(stdout);
}
int main()
{
    T=Read();
    while(T--)
    {
        Solve();
    }
}

详细

Test #1:

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

input:

2
4
3 0
1 3
1 1
0 0
1 1
1 1
3
0 0
999 1000
1000 999
1999 2000

output:

? 1 2
? 2 1
! 3 1
? 999 2
! 1999 2

result:

ok correct! (2 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

9
4
1 1
1 3
3 0
0 0
3 2
1 2
4
0 0
1 3
1 1
3 0
1 2
3 2
4
0 0
3 0
1 2
1 1
1 2
1 2
4
0 0
3 0
1 2
1 1
1 1
1 2
4
0 0
3 0
1 1
1 2
1 2
1 1
3
1000 0
0 0
0 1000
500 1
4
0 0
1000 0
1000 1000
0 1000
1000 1
5
0 1
1000 1000
1000 0
0 1000
1 0
1999 2
1000 1
9
4 1000
3 1
2 1000
3 1000
1 1
2 1
0 0
1 1000
4 0
500 1
1...

output:

? 1 2
? 2 1
! 5 2
? 1 2
? 2 1
! 7 2
? 1 2
? 2 1
! 3 2
? 1 2
? 2 1
! 2 1
? 1 2
? 2 1
! 5 2
? 500 1
! 500000 1
? 500 1
! 1000000 1
? 1 2
? 1001 2
! 1999999 2
? 1 2
? 3 2
? 5 2
? 7 2
! 4003 2

result:

ok correct! (9 test cases)

Test #3:

score: -100
Time Limit Exceeded

input:

78
8
951 614
927 614
957 614
957 604
937 614
942 619
951 610
927 604
10 1
25 2
21 2
10 1
7
562 260
602 250
582 255
587 260
602 260
562 250
577 260
10 1
15 2
15 2
10 1
3
454 98
494 68
455 68
117 8
3
526 589
566 559
527 559
117 8
3
854 496
854 466
894 466
15 1
3
797 264
827 254
857 264
5 1
3
719 737
7...

output:

? 932 1
? 1879 2
? 1893 2
? 954 1
! 317 1
? 1139 2
? 1159 2
? 1169 2
? 1189 2
! 375 1
? 909 2
! 585 1
? 1053 2
! 585 1
? 874 1
! 600 1
? 812 1
! 300 1
? 739 1
! 600 1
? 157 1
! 400 1
? 1489 2
? 1499 2
? 772 1
! 275 1
? 1869 2
? 1879 2
? 1889 2
? 1899 2
? 1909 2
? 1919 2
? 1929 2
? 1939 2
? 1949 2
? ...

result: