#include using namespace std; struct Point { int x, y; }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; int total = 2 * N; vector pts(total); for (int i = 0; i < total; i++){ cin >> pts[i].x >> pts[i].y; } // 固定缩放因子,使得 a, b 满足 |a|,|b|<=1e5 const int R = 100000; // 尝试候选方向次数(随机求解) const int candCount = 300; random_device rd; mt19937 gen(rd()); uniform_real_distribution dist(0, M_PI); for (int i = 0; i < candCount; i++){ double phi = dist(gen); int a = (int)round(R * cos(phi)); int b = (int)round(R * sin(phi)); if(a == 0 && b == 0) continue; // 计算所有点在方向 (a,b) 上的投影值 V = a*x + b*y vector V(total); for (int j = 0; j < total; j++){ V[j] = (long long)a * pts[j].x + (long long)b * pts[j].y; } // 利用 nth_element 快速求出排序后第 N-1 和第 N 个数 // 这里下标从0开始,第 N 个点对应下标 N-1,(N+1)th对应下标 N vector temp = V; //复制一份,不破坏原数组 nth_element(temp.begin(), temp.begin() + (N-1), temp.end()); long long lower = temp[N-1]; nth_element(temp.begin(), temp.begin() + N, temp.end()); long long upper = temp[N]; long long gap = upper - lower; // 情形1:gap >= 2,可直接选择 t = lower+1 if(gap >= 2){ int t = (int)(lower + 1); cout << a << " " << b << " " << -t << "\n"; return 0; } // 情形2:gap == 1,则考虑乘2的方案,但要求 |a|,|b| <= 50000 else if(gap == 1){ if(abs(a) <= 50000 && abs(b) <= 50000){ int tprime = (int)(2*lower + 1); cout << 2 * a << " " << 2 * b << " " << -tprime << "\n"; return 0; } } } // 理论上必定存在解,万一候选方向全部失效,则输出默认直线(不会到这一步) cout << "1 0 0\n"; return 0; }