QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#841438#9804. Guess the Polygonfrankly6TL 1ms3904kbC++172.0kb2025-01-03 19:01:502025-01-03 19:02:26

Judging History

This is the latest submission verdict.

  • [2025-01-03 19:02:26]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 3904kb
  • [2025-01-03 19:01:50]
  • Submitted

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#define int long long
using namespace std;
typedef long long ll;
typedef long double ld;
const int MX=1010;

int T, N;
map<ld,int> mp;
int read()
{
    int r=0, f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
    return r*f;
}
struct point
{
    ld x, y;
    bool operator < (const point &a)const{
        return x<a.x;
    }
}p[MX];
void ask(int u, int d)
{
    cout << "? " << u << " " << d << '\n';
    cout.flush();
}
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}
void print(ld x)
{
    ll d=1;
    while(x!=round(x)) x*=10, d*=10;
    // cout << "x=" << x << ", d=" << d << '\n';
    cout << "! " << ll(x/gcd(ll(x),d)) << " " << d/gcd(ll(x),d) << '\n';
    cout.flush();
}
signed main()
{
    // freopen("testdata.in","r",stdin);
    T=read();
    while(T--)
    {
        N=read();
        mp.clear();
        for(int i=1;i<=N;i++)
        {
            scanf("%Lf%Lf",&p[i].x,&p[i].y);
            mp[p[i].x]=1;
        }
        sort(p+1,p+1+N);
        ld ans=0, pre=0;
        if(mp.size()==N) //ask point
        {   
            for(int i=2;i<=N-1;i++)
            {
                ld h=(p[i].x-p[i-1].x)/2;
                ask(p[i].x,1);
                ld u, d;
                scanf("%Lf%Lf",&u,&d);
                u/=d;
                ans=ans+(pre+u)*h;
                pre=u;
            }
            ld hn=(p[N].x-p[N-1].x)/2;
            ans=ans+pre*hn;
        }
        else //ask median
        {
            for(int i=2;i<=N;i++)
            {
                if(p[i].x==p[i-1].x) continue;
                ask(p[i].x+p[i-1].x,2);
                ld u, d;
                scanf("%Lf%Lf",&u,&d);
                u/=d;               
                ans=ans+u*(p[i].x-p[i-1].x);
            }
        }
        print(ans);
    }
    return (0-0);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok correct! (2 test cases)

Test #2:

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

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
? 4 2
! 5 2
? 1 2
? 4 2
! 7 2
? 1 2
? 4 2
! 3 2
? 1 2
? 4 2
! 2 1
? 1 2
? 4 2
! 5 2
? 1000 2
! 500000 1
? 1000 2
! 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 4
3
526 589
566 559
527 559
117 4
3
854 496
854 466
894 466
15 1
3
797 264
827 254
857 264
10 1
3
719 737
...

output:

? 1864 2
? 1879 2
? 1893 2
? 1908 2
! 317 1
? 1139 2
? 1159 2
? 1169 2
? 1189 2
! 375 1
? 455 1
! 585 1
? 527 1
! 585 1
? 1748 2
! 600 1
? 827 1
! 300 1
? 1478 2
! 600 1
? 162 1
! 400 1
? 1489 2
? 1499 2
? 1544 2
! 275 1
? 1869 2
? 1879 2
? 1889 2
? 1899 2
? 1909 2
? 1919 2
? 1929 2
? 1939 2
? 1949 ...

result: