QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#822888 | #9804. Guess the Polygon | ucup-team2179# | ML | 0ms | 0kb | C++20 | 8.6kb | 2024-12-20 17:14:48 | 2024-12-20 17:14:49 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
class Int {
public:
using ll = long long;
Int() {};
Int(const string& s);
Int(ll a) :Int(to_string(a)) {}
Int(const Int& bInt) :nums(bInt.nums), isPositive(bInt.isPositive), length(bInt.length) {}
Int(Int&& bInt) noexcept :nums(move(bInt.nums)), isPositive(bInt.isPositive), length(bInt.length) {}
Int(const vector<int>& vec, bool sign = true) :nums(vec), isPositive(sign) { cutLeadZero(); }
friend istream& operator >>(istream& is, Int& bInt) {
string s;
is >> s;
bInt = move(Int(s));
return is;
}
friend ostream& operator <<(ostream& os, const Int& bInt);
operator string() const;
const Int& operator +() const { return *this; }
Int operator -() const {
Int tmp(*this);
if (!tmp.isZero())
tmp.isPositive = !isPositive;
return tmp;
}
bool operator <(const Int& bInt) const;
bool operator <=(const Int& bInt) const;
bool operator ==(const Int& bInt) const;
Int operator +(const Int& bInt) const;
Int operator -(const Int& bInt) const;
Int operator *(const Int& bInt) const;
// 除法会返回 商和余数
pair<Int, Int> operator /(const Int& bInt) const;
int operator[](int idx) const { return nums[idx]; }
Int& operator =(const Int& bInt) {
if (bInt == *this)
return *this;
nums = bInt.nums;
isPositive = bInt.isPositive;
length = bInt.length;
return *this;
}
Int& operator =(Int&& bInt)noexcept {
nums = move(bInt.nums);
isPositive = bInt.isPositive;
length = bInt.length;
return *this;
}
size_t size() const { return nums.size(); }
void cutLeadZero();
bool isZero() const;
Int absValue() const {
return move(Int(nums));
}
static Int e(size_t n) {
if (n <= 0)
return move(Int(vector<int>(1, 1)));
int m = n / digit;
n -= m * digit;
vector<int> ans(m);
string s = "1";
s += move(string(n, '0'));
ans.push_back(stoi(s));
return move(Int(ans));
}
private:
// 低位到高位
vector<int> nums;
bool isPositive = 1;
int length = 0;
static int digit;
static int mod;
};
int Int::digit = 8;
int Int::mod = 100000000;
Int::Int(const string& s) {
int n = s.size(), minIdx = 0;
if(s[0]=='-')
isPositive = false, minIdx = 1;
else if(s[0]=='+')
isPositive = true, minIdx = 1;
for (int i = n - 1; i >= minIdx; i -= digit) {
int beg = max(minIdx, i - digit + 1);
nums.push_back(stoi(s.substr(beg, i - beg + 1)));
}
cutLeadZero();
}
ostream& operator <<(ostream& os, const Int& bInt) {
os << (string)bInt;
return os;
}
Int::operator string() const {
string ans;
if (!isPositive)
ans += "-";
int n = nums.size();
for (int i = n - 1; i >= 0; i--) {
string s = to_string(nums[i]);
if (i != n - 1)
ans += string(digit - s.size(), '0');
ans += s;
}
return ans;
}
bool Int::operator<(const Int& bInt) const {
if (isPositive && !bInt.isPositive)
return false;
if (!isPositive && bInt.isPositive)
return true;
bool flag = true;
if (!isPositive)
flag = false;
if (length < bInt.length)
return flag;
else if (length > bInt.length)
return !flag;
int n = size();
for (int i = n - 1; i >= 0; i--) {
if (nums[i] < bInt[i])
return flag;
else if (nums[i] > bInt[i])
return !flag;
}
return false;
}
bool Int::operator<=(const Int& bInt) const {
if (isPositive && !bInt.isPositive)
return false;
if (!isPositive && bInt.isPositive)
return true;
bool flag = true;
if (!isPositive)
flag = false; // 都为负数
if (length < bInt.length)
return flag;
else if (length > bInt.length)
return !flag;
int n = size();
for (int i = n - 1; i >= 0; i--) {
if (nums[i] < bInt[i])
return flag;
else if (nums[i] > bInt[i])
return !flag;
}
return true;
}
bool Int::operator==(const Int& bInt) const {
if (length != bInt.length)
return false;
int n = size();
for (int i = 0; i < n; i++)
if (nums[i] != bInt[i])
return false;
return true;
}
Int Int::operator+(const Int& bInt) const {
if (!bInt.isPositive)
return *this - (-bInt);
if (!isPositive)
return bInt - (-*this);
vector<int> ans;
int n = size(), m = bInt.size(), sum = 0, i = 0, j = 0;
while (i < n || j < m || sum)
{
if (i < n)
sum += nums[i++];
if (j < m)
sum += bInt[j++];
ans.push_back(sum % mod);
sum /= mod;
}
return move(Int(ans, isPositive));
}
Int Int::operator-(const Int& bInt) const
{
if (!bInt.isPositive)
return *this + (-bInt);
if (!isPositive)
return -((-*this) + bInt);
if (*this < bInt)
return -(bInt - *this);
vector<int> ans;
int i = 0, j = 0, n = size(), m = bInt.size(), sum = 0;
while (i < n || j < m || sum) {
if (i < n)
sum += nums[i++];
if (j < m)
sum -= bInt[j++];
int flag = 0;
if (sum < 0) {
flag = -1;
sum += mod;
}
ans.push_back(sum);
sum = flag;
}
return move(Int(ans));
}
Int Int::operator*(const Int& bInt) const {
int n = size(), m = bInt.size();
vector<int> ans(n + m);
using ll = long long;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ll tmp = ans[i + j] + nums[i] * 1ll * bInt[j];
ans[i + j] = tmp % mod;
ans[i + j + 1] += tmp / mod;
}
}
return move(Int(ans, isPositive == bInt.isPositive));
}
pair<Int, Int> Int::operator/(const Int& bInt) const {
Int a = absValue();
Int b = bInt.absValue();
if (b.isZero())
return pair<Int, Int>(*this, move(b));
if (a < b)
return pair<Int, Int>(move(Int(0)), *this);
int len = a.length - b.length + 1;
string ans;
if (isPositive != bInt.isPositive)
ans = "-";
for (int i = 0; i < len; i++) {
Int tmp = e(len - i - 1) * b;
int times = 0;
while (tmp <= a) {
a = a - tmp;
++times;
}
ans += times + '0';
}
a.isPositive = isPositive;
return pair<Int, Int>(move(Int(ans)), move(a));
}
void Int::cutLeadZero() {
while(nums.size() > 1 && nums.back() == 0)
nums.pop_back();
if(nums.empty()) length = 0;
else length = (nums.size() - 1) * digit + to_string(nums.back()).size();
}
bool Int::isZero() const {
return nums.size() == 1 && nums.back() == 0;
}
Int biggcd(Int a,Int b){
if(b==Int(0ll))return a;
if(a<b)swap(a,b);
return biggcd(b,(a/b).second);
}
struct num{
Int a,b;
num(Int x,Int y){
Int d=biggcd(x,y);
a=(x/d).first;
b=(y/d).first;
}
num(){a=0,b=1;}
num(Int x){
a=x;
b=1;
}
num operator+(num y){
return num(a*y.b+y.a*b,b*y.b);
}
num operator*(num y){
return num(a*y.a,b*y.b);
}
num operator/(num y){
return num(a*y.b,b*y.a);
}
num operator-(num y){
return num(a*y.b-y.a*b,b*y.b);
}
};
struct Point
{
num x,y;
Point(){}
Point(num a,num b){
x=a,y=b;
}
};
num getval(Point a1,Point a2,num x){
auto [x1,y1]=a1;
auto [x2,y2]=a2;
return y1+(y2-y1)/(x2-x1)*(x-x1);
}
num query(num u){
cout<<"? "<<u.a<<" "<<u.b<<endl;
int x,y;
cin>>x>>y;
return num(x,y);
}
num diff=num(1,5);
void solve() {
int n;
cin>>n;
vector<int>vx;
map<int,int>mp;
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
mp[x]++;
}
for(auto [x,cnt]:mp){
vx.pb(x);
}
n=vx.size();
Point val[n][2];
num ans(0);
if(mp[vx[0]]>1){
num now=query(num(vx[0])+diff);
val[0][1]=Point(num(vx[0])+diff,now);
}
else {
num now=num(0);
val[0][1]=Point(num(vx[0]),now);
}
if(mp[vx[n-1]]>1){
num now=query(num(vx[n-1])-diff);
val[n-1][0]=Point(num(vx[n-1])-diff,now);
}
else {
num now=num(0);
val[n-1][0]=Point(num(vx[n-1]),now);
}
for(int i=1;i<n-1;i++){
if(mp[vx[i]]==1){
num now=query(num(vx[i]));
val[i][0]=Point(num(vx[i]),now);
val[i][1]=Point(num(vx[i]),now);
}
else {
num now=query(num(vx[i])-diff);
val[i][0]=Point(num(vx[i])-diff,now);
now=query(num(vx[i])+diff);
val[i][1]=Point(num(vx[i])+diff,now);
}
}
for(int i=0;i<n-1;i++){
num high=num(vx[i+1]-vx[i]);
num len1=getval(val[i][1],val[i+1][0],num(vx[i]));
num len2=getval(val[i][1],val[i+1][0],num(vx[i+1]));
ans=ans+high*(len1+len2)/num(2);
}
cout<<"! "<<ans.a<<" "<<ans.b<<endl;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
詳細信息
Test #1:
score: 0
Memory Limit Exceeded
input:
2 4 3 0 1 3 1 1 0 0 8 5 9 5
output:
? 4 5 ? 6 5