Программа в Си задача №90 acmp.ru

[kkhr]

Здравствуйте, не могу найти ошибку в программе, на 6 тесте проваливается.

Эта история происходила на одной плоской планете. С незапамятных времен на ней существовал город N, находящийся в точке xn,yn. Кроме этого, в разное время на этой же планете существовали страны, каждая из которых имела форму треугольника.

Теперь перед историками встала серьезная задача — по имеющимся у них данным о треугольных странах определить, в какие страны мог входить город N. Город мог входить в страну, если он находится строго внутри нее.

Входные данные
Первая строка входного файла содержит два числа: xn и yn — координаты города N. Вторая строка входного файла содержит количество k треугольных стран (1 ≤ k ≤ 1000). Последующие k строк каждая описывают одну треугольную страну. Описание треугольной страны состоит из шести целых чисел x1,y1,x2,y2,x3,y3, где (x1,y1), (x2,y2), (x3,y3) — координаты вершин этой страны.

Гарантируется, что все страны имеют ненулевую площадь. Все координаты не превосходят 10000 по абсолютной величине.

Выходные данные
В первой строке выходного файла выведите количество стран, в которые мог входить город N. Во второй строке выведите через пробел номера этих стран в возрастающем порядке. Страны нумеруются с единицы в том порядке, в каком они заданы во входном файле.


Безымянный12.png

#include <stdio.h> 
long long check(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y) { 

if ((((x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y)) > 0) && 
(((x2 - x) * (y3 - y2) - (x3 - x2) * (y2 - y)) > 0) && 
(((x3 - x) * (y1 - y3) - ((x1- x3) * (y3 - y)) > 0))) 
return 1; 
else return 0; 
} 
int main() 
{ 
int x, y; 
int j,i; 
scanf("%d%d",&x,&y); 
int n; 
scanf("%d",&n); 
int a[6]; 
  int k=0, ak[10000];
for (i=0;i<n;i++) { 
ak[i] = 0; 
} 
for (j=1;j<n + 1;j++) { 
int i; 
for (i=0; i<6;i++) 
{ 
scanf("%d",&a[i]); 
} 
if (check(a[0], a[1], a[2], a[3], a[4], a[5], x, y)) { 

ak[j-1]=j; 
k++; 
} 

} 
printf("%d\n",k); 

for (i = 0;i < n;i++) { 
if (ak[i]!=0) 
printf("%d ",ak[i]); 
} 

return 0;

[Аватар]

А чего проверка на положительность? Знак зависит от обхода сторон - по часовой или против часовой. А у тебя не известно. Так что нужно проверять - а одинаков ли знак

[Black Fregat]

Более формально, нужно проверять, чтобы знак был тот же, что и при подстановке третьей вершины

[kkhr]

А как это проверить?