QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#841433 | #9804. Guess the Polygon | frankly6 | TL | 1ms | 3972kb | C++17 | 2.0kb | 2025-01-03 19:00:47 | 2025-01-03 19:00:52 |
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 << "! " << 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: 3972kb
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: -100
Time Limit Exceeded
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
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 ! 1e+06 1