ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1207. Медиана на плоскости

Please help, why WA on test #6?
Послано Natasha 15 апр 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;
}