Здесь условие задачи http ://acm.timus.ru/problem.aspx?space=1&num=1875
Не могу написать программу.
Математическое решение выглядит как-то так:
считаем коэффициенты квадратного уравнения a и b для всех возможных пар точек:
a = (y1x2 - y2x1) /( x1x2(x1-x2) )
b = (y1-y2) / (x1-x2) - a(x1+x2)
и тогда, если выполняется условие (a<0&&b!=0) получаем две точки, лежащие на одной параболе.
Затем проверяем не лежит ли третья точка на этой параболе
y3x1x2(x1-x2) = (y1x2 - y2x1) x32 + (y2x12 - y1x22) x3
ну и так для всех точек.
Я что-то упускаю и уже несколько дней ничего не могу придумать. Написал кое-что, но даже показывать стыдно. Разумеется не работает, что не удивительно.
Код:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define N 5
bool Pass (int a, int b, int c);
bool func (int i, int j);
struct point {
int x;
int y;
};
int main()
{
int i,j,k,bird=5;
struct point P[N];
FILE* input = fopen ("input.txt", "r");
if (!input) {
printf ("Can not open file");
return 0;
}
for (i = 0; i<N; i++)
{
fscanf (input, "%d%d", &P[i].x, &P[i].y);
printf ("x= %d y= %d\n",P[i].x, P[i].y);
}
fclose (input);
for (i = 0; i<N; i++)
{
for (j = i+1; j<N; j++)
{
if (func(i,j))
{
bird = 4;
for (k = j+1; k<N; k++)
{
if (Pass(i, j, k))
bird--;
}
}
}
}
printf("bird = %d",bird);
getch();
return 0;
}
bool func (int i, int j)
{
struct point P[N];
double a = (P[i].y*P[j].x-P[j].y*P[i].x) / (P[i].x*P[j].x*(P[i].x-P[j].x));
double b = (P[i].y-P[j].y)/(P[i].x-P[j].x)-a*(P[i].x+P[j].x);
printf("a= %f, b= %f\n",a,b);
return (a<0 && b!=0);
}
bool Pass(int a, int b, int c)
{
struct point P[N];
return (P[a].x * P[a].x) * P[b].x * P[c].y +
P[a].x * P[b].y * (P[c].x * P[c].x) +
P[a].y * (P[b].x * P[b].x) * P[c].x -
(P[a].x * P[a].x) * P[b].y * P[c].x -
P[a].x * (P[b].x * P[b].x) * P[c].y -
P[a].y * P[b].x * (P[c].x * P[c].x) == 0;
}