QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#795192#9804. Guess the Polygonucup-team3670#RE 1ms3552kbC++201.6kb2024-11-30 18:30:182024-11-30 18:30:24

Judging History

This is the latest submission verdict.

  • [2024-11-30 18:30:24]
  • Judged
  • Verdict: RE
  • Time: 1ms
  • Memory: 3552kb
  • [2024-11-30 18:30:18]
  • Submitted

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;
		assert(!q.empty());
		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: 3552kb

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
Runtime Error

input:

9
4
1 1
1 3
3 0
0 0
3 1
3 1

output:

? 1 1
? 1 1
! 9 2

result: