QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#795914 | #9804. Guess the Polygon | ucup-team1134# | WA | 1ms | 3740kb | C++23 | 3.2kb | 2024-12-01 04:10:30 | 2024-12-01 04:10:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;
//有理数
ll gcd(ll a,ll b){
if(b==0) return a;
return gcd(b,a%b);
}
struct Rational{
ll x,y;
Rational(ll x=0,ll y=1):x(x),y(y){}
Rational operator + (Rational p){
ll z=y/gcd(y,p.y)*p.y;
ll nx=z/y*x+z/p.y*p.x,ny=z;
ll g=gcd(abs(nx),ny);
return Rational(nx/g,ny/g);
}
Rational operator - (Rational p){
ll z=y/gcd(y,p.y)*p.y;
ll nx=z/y*x-z/p.y*p.x,ny=z;
ll g=gcd(abs(nx),ny);
return Rational(nx/g,ny/g);
}
Rational operator * (Rational p){
ll nx=x*p.x,ny=y*p.y;
if(ny<0){
nx*=(-1);
ny*=(-1);
}
ll g=gcd(abs(nx),abs(ny));
return Rational(nx/g,ny/g);
}
Rational operator / (Rational p){
ll nx=x*p.y,ny=y*p.x;
if(ny<0){
nx*=(-1);
ny*=(-1);
}
ll g=gcd(abs(nx),abs(ny));
return Rational(nx/g,ny/g);
}
bool operator < (const Rational &p)const{
return x*p.y<y*p.x;
}
bool operator == (const Rational &p)const{
return x*p.y==y*p.x;
}
};
int main(){
int Q;cin>>Q;
while(Q--){
ll N;cin>>N;
vll S;
vl use;
for(int i=0;i<N;i++){
ll a,b;cin>>a>>b;
use.pb(a);
S.pb(mp(a,b));
}
sort(all(S));
mkunique(use);
int l=0;
vector<Rational> X;
for(int i=0;i<si(use);i++){
int r=l;
while(r<N&&S[r].fi==use[i]) r++;
if(i==0||i==si(use)-1){
if(r-l>1){
cout<<"? "<<use[i]<<" "<<1<<endl;
ll a,b;cin>>a>>b;
X.pb(Rational{a,b});
}else{
X.pb(Rational{0,1});
}
}else{
cout<<"? "<<use[i]<<" "<<1<<endl;
ll a,b;cin>>a>>b;
X.pb(Rational{a,b});
}
l=r;
}
Rational ans={0,1};
for(int i=0;i+1<si(use);i++){
Rational su=X[i]+X[i+1];
su=su*(use[i+1]-use[i]);
ans=ans+su;
}
ans=ans*Rational{1,2};
cout<<"! "<<ans.x<<" "<<ans.y<<endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3740kb
input:
2 4 3 0 1 3 1 1 0 0 2 1 3 0 0 999 1000 1000 999 1999 1000
output:
? 1 1 ! 3 1 ? 999 1 ! 1999 2
result:
ok correct! (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3524kb
input:
9 4 1 1 1 3 3 0 0 0 3 1
output:
? 1 1 ! 9 2
result:
wrong answer the answer is incorrect, expect: 5/2, find: 9/2 (test case 1)