QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#822163 | #9804. Guess the Polygon | ucup-team3548 | TL | 0ms | 3728kb | C++20 | 3.0kb | 2024-12-19 22:54:03 | 2024-12-19 22:54:04 |
Judging History
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 ? ...