C++ Задача на геометрию

[UaKot]

Задача с acmp "Башни-2"

Для того, чтобы защититься от некоторых соседей, король решил построить стену, имеющую форму отрезка. С некоторыми соседями король находится в хороших отношениях, а некоторым готовится объявить войну. Король решил не загораживаться от друзей очень высокой стеной. Однако, стена, отделяющая его от врагов, должна быть достаточно высокой. Было решено, что для наблюдения за прилежащей территорией нужно построить башни. При этом, на участках между башнями высота стен должна изменяться равномерно.

После того, как стена и башни были построены, король заметил, что башни могут быть использованы для наблюдения за состоянием других башен. Однако, некоторые башни оказались очень высокими и загородили другие.

Для каждой башни король попросил вас выяснить, сколько других башен из нее видно.

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

В первой строке входного файла INPUT.TXT находится n (2 ≤ n ≤ 2000) - количество башен стены. В следующих n строках находятся натуральные числа xi и hi (0 ≤ xi ≤ 100000, 1 ≤ hi ≤ 10000) - координата и высота i-ой башни. Все xi различны.

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

Выходной файл OUTPUT.TXT должен содержать n строк. В i-ой строке выведите количество башен, которые видно из башни номер i.

Моя программа:

#include <stdio.h>
#include <fstream>
#include <iostream>

struct tower{ //Башенка :)
	int n; //Ее порядковый номер (потеряется во время сортировки, нужно помнить)
	int x; //Координата
	int y; //Высота
};

tower t[2000]; //Много башенок :)

void qsort(int l, int r){
	int m = t[(l+r)/2].x;
	int i = l;
	int j = r;
	while (i <= j){
		while (t[i].x < m) i++;
		while (t[j].x > m) j--;
		if (i <= j){
			std::swap(t[i], t[j]);
			i++;
			j--;
		}
	}
	if (i < r) qsort(i, r);
	if (j > l) qsort(l, j);
}

void generate(double x1, double x2, double y1, double y2, double &k, double &b){ //Генерация коэффициентов уравнения прямой
	k = (y1-y2)/(x1-x2);
	b = y1 - k*x1;
}

bool high(double x, double y, double k, double b){ //Проверка на то, пересекает ли отрезок, соединяющий башенки, другие башни
	if (y > k*x + b)
		return true;
	return false;
}

int main(){
	FILE *in=fopen("input.txt", "r");
	FILE *out=fopen("output.txt", "w");

	int h[2000] = {0};
	int N;
	fscanf(in, "%d", &N);
	for(int i = 0; i < N; i++){
		fscanf(in, "%d%d", &t[i].x, &t[i].y);
		t[i].n = i;
	}
	int j;
	double k, b;
	qsort(0, N-1);
 	for(int i = 0; i < N; i++){ // Перебираем все башни
		int m = t[i].y;//Максимальная высота
		for(j = i + 1; m > t[j].y && j < N; j++){ // Пока мы не нашли башню выше, проверяем на обозрение все соседние
			h[t[i].n]++;
			h[t[j].n]++; // Кандидат
			generate(t[i].x, t[j].x, t[i].y, t[j].y, k, b);
			for(int g = i+1; g < j; g++) //Проверяем кандидата
				if(high(t[g].x, t[g].y, k, b)){ // Если кандидат не прошел проверку
					h[t[i].n]--;
					h[t[j].n]--; // То он нам не нужен 
					break;
				}
		}
		if(j < N){ 
			h[t[i].n]++;
			h[t[j].n]++;
			m = t[j].y;
			j++;
		}
		while(j < N){ //Мы нашли башню выше первой, дальше просто:
			if(t[j].y > m){ // Если мы нашли башню еще выше
				m = t[j].y; // Делаем ее максимальной высоты
				h[t[i].n]++; // С первой башни видно ее
				h[t[j].n]++; // И с нее, разумеется, видно первую
			}
			j++;
		}
	}
	for (int i = 0; i < N; i++)
		fprintf(out, "%d\n", h[i]);
}

Выдает неправильный ответ на 5 тесте. Алгоритм не верный, или есть недочет?

Идея решения: башни видно друг с друга, если отрезок, соединяющий их вершины не пересекает вершины других башен, но такую проверку достаточно сделать для башен, начиная с i, пока не встретим первую башню, больше ее, затем плюсуем только башни, оказавшиеся выше найденной, потому что они всяко должны подходить, а другие они перекрывают собой