#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 = 3000; 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; // 计算所有点的投影值 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-index:第 N 个点下标 N-1,下一点下标 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]; // 当存在 gap(要求 gap>=2,这样就能选择一个整数 t 避免落在某个点上) if(lower < upper && (upper - lower) >= 2){ int t = (int)(lower + 1); cout << a << " " << b << " " << -t << "\n"; return 0; } } // 理论上必定存在解,万一找不到则输出默认直线(不会到这一步) cout << "1 0 0\n"; return 0; }