题目说明：二维坐标上有一堆点，选两点作为一条直线，把所有点分成两堆
题目解析：极角排序。找到x轴最小的点，其他所有点求atan2，进行排序，取最小点和排列后中间点的index索引输出。
Problem analysis English version:
- Find minimum x in points.
- Store atan2 which is theta between minimum x and origin and the index of each point.
- Use bubble sort to sort atan2 result.
- Output the index of minimum x and the number in the middle of the series.
代码说明：个人写了冒泡排序，没用c++ sort 和结构体，相对来说代码可读性较差，可以对此进行改进
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<iostream> #include<cmath> using namespace std; int main() { int n; cin >> n; double array[10000][2]; double theta[10000]; int position[10000]; for (int i = 0; i < n; i++)cin >> array[i][0] >> array[i][1]; int min = array[0][0]; int minPosition = 0; for (int i = 1; i < n; i++) { minPosition = min <= array[i][0] ? minPosition : i; min = min <= array[i][0] ? min : array[i][0]; } int ii = 0; for (int i = 0; i < n; i++) { if (i == minPosition)continue; position[ii] = i + 1; theta[ii] = atan2(array[i][1] - array[minPosition][1], array[i][0] - array[minPosition][0]); ii++; } double temp; for (int i = 0; i < n - 2; i++) { for (int j = 0; j < n - i - 2; j++) { if (theta[j + 1] < theta[j]) { temp = theta[j]; theta[j] = theta[j + 1]; theta[j + 1] = temp; temp = position[j]; position[j] = position[j + 1]; position[j + 1] = temp; } } } cout << minPosition + 1 << " " << position[(n - 1) / 2]<< endl; return 0; } |
浙公网安备 33010902002953号