|
|
back to boardPlease help, why WA on test #6? Posted by Natasha 15 Apr 2016 16:12 //1152 #include <iostream> #include <vector> #include <cmath> using namespace std; int main() { int n, x0, y0, index0; cin >> n; if (n == 2){ cout << 1 + ' ' + 2; } else { vector<vector<int>> p(n, vector<int>(2)); // [x, y] vector<double> k(n); for (int i = 0; i < n; i++) { cin >> p[i][0] >> p[i][1]; } x0 = y0 = 2147483647; for (int i = 0; i < n; i++) { if (p[i][0] < x0 ||p[i][0] == x0 && p[i][1] < y0){ x0 = p[i][0]; y0 = p[i][1]; index0 = i; } } for (int i = 0; i < n; i++) { //y = kx + m if (i == index0) { k[i] = 9223372036854775807; } else { if (x0 == p[i][0]) { k[i] = 9223372036854775807; } else { k[i] = (p[i][1] - y0) / (p[i][0] - x0); } } }
vector<int> d(n); for (int i = 0; i < n; i++) { d[i] = i; } double tempD; int tempI; for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < i; j++) { if (k[j + 1] < k[j]) { tempD = k[j + 1]; k[j + 1] = k[j]; k[j] = tempD; tempI = d[j + 1]; d[j + 1] = d[j]; d[j] = tempI; } } } cout << index0 + 1 << ' ' << d[n / 2 -1] + 1; } return 0; } |
|
|