QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#841438 | #9804. Guess the Polygon | frankly6 | TL | 1ms | 3904kb | C++17 | 2.0kb | 2025-01-03 19:01:50 | 2025-01-03 19:02:26 |
Judging History
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 ...