QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#795173 | #9804. Guess the Polygon | ucup-team3670# | WA | 1ms | 3612kb | C++20 | 1.6kb | 2024-11-30 18:17:11 | 2024-11-30 18:17:13 |
Judging History
answer
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
using namespace std;
const int MOD = (int)(1e9) + 7;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
if (a < 0)
a += MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
int binpow(int a, int b){
int res = 1;
while (b){
if (b & 1)
res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
struct point{
int x, y;
};
int get(string s){
int res = 0;
for (char c : s) if (isdigit(c))
res = add(mul(res, 10), c - '0');
return res;
}
void solve(){
int n;
cin >> n;
vector<point> a(n);
forn(i, n) cin >> a[i].x >> a[i].y;
sort(a.begin(), a.end(), [](const point &a, const point &b){
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
});
vector<pair<int, int>> inter(n, {0, 1});
for (int i = 1; i < n - 1; ++i){
cout << "? " << a[i].x << " " << 1 << endl;
string p, q;
cin >> p >> q;
inter[i] = {get(p), get(q)};
if (inter[i].first == 0) inter[i].second = 1;
assert(inter[i].second != 0);
}
if (a[0].x == a[1].x) inter[0] = inter[1];
if (a[n - 1].x == a[n - 2].x) inter[n - 1] = inter[n - 2];
int ans = 0;
forn(i, n - 1){
int s1 = mul(inter[i].first, binpow(inter[i].second, MOD - 2));
int s2 = mul(inter[i + 1].first, binpow(inter[i + 1].second, MOD - 2));
ans = add(ans, mul(add(s1, s2), a[i + 1].x - a[i].x));
}
int g = __gcd(ans, 2);
cout << "! " << ans / g << " " << 2 / g << endl;
}
int main(){
int tc;
cin >> tc;
while (tc--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3548kb
input:
2 4 3 0 1 3 1 1 0 0 2 1 2 1 3 0 0 999 1000 1000 999 1999 1000
output:
? 1 1 ? 1 1 ! 3 1 ? 999 1 ! 1999 2
result:
ok correct! (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3612kb
input:
9 4 1 1 1 3 3 0 0 0 3 1 3 1
output:
? 1 1 ? 1 1 ! 9 2
result:
wrong answer the answer is incorrect, expect: 5/2, find: 9/2 (test case 1)