целочисленные координаты

Задача

Антон в школе начал изучать математику. Его внимание привлекло новое для него понятие числовой прямой. Антон быстро научился вычислять расстояния между двумя точками на этой прямой, задавать отрезки и интервалы на ней.

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: На числовой прямой задано $n$ точек. Необходимо найти среди них две ближайшие. Расстояние между двумя точками числовой прямой $x$ и $y$ равно $|x-y|$.

Требуется написать программу, которая поможет Антону решить поставленную задачу.

Входные данные

Первая строка содержит количество точек $n$ $\left(2\leq n \leq 10^{5}\right)$. Вторая строка содержит $n$ различных целых чисел $x_{i}$- координаты заданных точек числовой прямой. Числа в строке разделены пробелом. Значение любой координаты $x_{i}$ не превосходит $10^{9}$
по абсолютной величине.

Выходные данные

В первой строке вывести минимальное расстояние между двумя заданными точками. Во второй строке вывести номера точек, которым соответствует найденное расстояние. Точки нумеруются натуральными числами от $1$ до $n$ в том же порядке, в котором они заданы во входе. Если ответов несколько, выведите любой из них.

Тесты

Входные данные	Выходные данные
5 10 3 6 2 5	1 2 4
6 10 3 6 1 5 11	1 3 5
9 14545690 4343 -6 10 500 1100 -1 2 10	0 4 9
2 1 5	4 2 1
2 -1000000000 1000000000	2000000000 2 1
9 1 5 9 15 3 100 -1 4 10	1 8 5
10 0 1 5 10 20 100 120 250 -100 55	1 2 1

Решение

#include <iostream>
#include <map>
using namespace std;

int main() {
    long long n;
    cin >> n;
    map<long long, long long> Ox;
    long long dis = 0,A = 0,B = 0;//dis- distance
    bool zero_dis = 0;
    for(long long i = 1;i <= n && !zero_dis;i++){
        long long tmp;
        cin >> tmp;
        if(Ox[tmp] != 0){
            zero_dis = true;
            A = Ox[tmp];
            B = i;
            dis = 0;
        }
        else Ox[tmp] = i;
    }
    
    if(!zero_dis){
        dis = -1;
        for(auto i = Ox.begin(),j = ++Ox.begin(); j != Ox.end(); i++, j++){
            long long tmp_dis = j->first - i->first;
            if(dis>tmp_dis || dis<0){
                dis = tmp_dis;
                A = j->second;
                B = i->second;
            }
        }
    }
    cout << dis << "\n" << A << " " << B;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

long long n;

cin >> n;

map<long long, long long> Ox;

long long dis = 0,A = 0,B = 0;//dis- distance

bool zero_dis = 0;

for(long long i = 1;i <= n && !zero_dis;i++){

long long tmp;

cin >> tmp;

if(Ox[tmp] != 0){

zero_dis = true;

A = Ox[tmp];

B = i;

dis = 0;

}

else Ox[tmp] = i;

}

if(!zero_dis){

dis = -1;

for(auto i = Ox.begin(),j = ++Ox.begin(); j != Ox.end(); i++, j++){

long long tmp_dis = j->first - i->first;

if(dis>tmp_dis || dis<0){

dis = tmp_dis;

A = j->second;

B = i->second;

}

cout << dis << "\n" << A << " " << B;

return 0;

}

Объяснение

В начале создаётся ассоциативный контейнер, где каждой точке на прямой ставится в соответствие её номер. Попутно выполняется проверка, не было ли до этого точки с такой же координатой (тогда расстояние между ними равно $0$, соответственно). Затем, поскольку map автоматически выполняет сортировку, сравниваем разность координат рядом стоящих элементов с текущим минимальным расстоянием, и, при необходимости, обновляем значение расстояния и индексы точек, для которых это расстояние верно.

Замечание

Видимо, тесты e-olymp не требуют проверки на случай, если точки совпадают. Тем не менее, я решил оставить это в коде, поскольку в условии не оговорено недопустимости этой ситуации

e-olymp

ideone

Related Images:

Задача

На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.

Входные данные

В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].

Тесты

Входные данные	Выходные данные
5 2 -1 3 0 0 4 -3 0 -2 1	6
5 0 0 2 4 6 6 10 34 -42 -48	10
4 0 0 0 1 1 0 1 1	0
8 0 0 2 2 1 1 3 3 0 1 2 1 1 0 1 2	24
5 0 0 0 1 -1 0 -1 -1 3 -3	3

Входные данные

Выходные данные

5
2 -1
3 0
0 4
-3 0
-2 1

5
0 0
2 4
6 6
10 34
-42 -48

4
0 0
0 1
1 0
1 1

8
0 0
2 2
1 1
3 3
0 1
2 1
1 0
1 2

5
0 0
0 1
-1 0
-1 -1
3 -3

#include <iostream>
using namespace std;
 
int main() {
    unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0};
    unsigned long long c = 0;
    cin >> n;
    for (int i = 0; i < n; i ++){
        cin >> x1 >> y1;
        if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++;
        else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++;
        else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++;
        else A [3] ++;
    }
    for(int i = 0; i < 4; i ++){
        for(int  j= 0; j < 4; j ++){
            if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6;
            else c += A[i] * (A[i] - 1) * A[j] / 2;
        }       
    }
    cout << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0};

unsigned long long c = 0;

cin >> n;

for (int i = 0; i < n; i ++){

cin >> x1 >> y1;

if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++;

else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++;

else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++;

else A [3] ++;

}

for(int i = 0; i < 4; i ++){

for(int j= 0; j < 4; j ++){

if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6;

else c += A[i] * (A[i] - 1) * A[j] / 2;

}

cout << c;

return 0;

}

Решение задачи

Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex]. Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.