#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; // 候选角数量,此处选100即可(区间[0,π)) const int candCount = 100; for (int i = 0; i < candCount; i++){ // 取候选角 φ 在 [0, π) 均匀分布 double phi = (double)i * M_PI / candCount; // 计算 a, b 取整 int a = (int)round(R * cos(phi)); int b = (int)round(R * sin(phi)); if(a == 0 && b == 0) continue; // 对所有点计算投影值 V_i = a*x + b*y vector V(total); for (int j = 0; j < total; j++){ // 注意:由于 a,b,x,y 均为整数,V[i] 也是整数 V[j] = a * pts[j].x + 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()); int lower = temp[N-1]; nth_element(temp.begin(), temp.begin() + N, temp.end()); int upper = temp[N]; // 判断是否存在缺口:要求 lower < t < upper 有整数 t if(lower < upper && (upper - lower) >= 2){ int t = lower + 1; // 即选择 t,使得 lower < t < upper // 构造直线: a * x + b * y - t = 0 => c = -t cout << a << " " << b << " " << -t << "\n"; return 0; } } // 理论上必有一方向可行,万一候选方向全部失效则输出默认直线 cout << "1 0 0\n"; return 0; }