| Главная » Статьи » Задачи из заказов » Заказ 07.03.08 |
Из заданного множества точек на плоскости выбрать такие три точки, чтобы они образовывали треугольник, внутри которого находилось бы...
| // 1.3 Из заданного множества точек на плоскости выбрать такие три // точки, чтобы они образовывали треугольник, внутри которого находилось // бы максимальное количество точек множества. #include <stdio.h> #include <conio.h> void main() { clrscr(); const eps = 1e-3; const nmax = 100; int n, r1 = 0, r2 = 0, r3 = 0; float x[nmax], y[nmax]; int maxcount = 0; printf("Vvedite kolvo tochek: "); scanf("%d", &n); for (int i = 0; i < n; i++) { printf("x[%d] = ", i); scanf("%f", &x[i]); printf("y[%d] = ", i); scanf("%f", &y[i]); } for (int t1 = 0; t1 < n; t1++) for (int t2 = 0; t2 < n; t2++) for (int t3 = 0; t3 < n; t3++) { int count = 0; for (int t = 0; t < n; t++) { if ((t != t1) && (t != t2) && (t != t3) && (t1 != t2) && (t2 != t3)) { float v = (x[t]-x[t1])*(y[t2]-y[t1])-(y[t]-y[t1])*(x[t2]-x[t1]); if ((((x[t]-x[t2])*(y[t3]-y[t2])-(y[t]-y[t2])*(x[t3]-x[t2]))*v>-eps) && (((x[t]-x[t3])*(y[t1]-y[t3])-(y[t]-y[t3])*(x[t1]-x[t3]))*v>-eps)) count++; } } if (count > maxcount) { maxcount = count; r1 = t1; r2 = t2; r3 = t3; } } printf("Treugolnik s vershinami %d, %d, %d. kolvo tochek vnutri %d", r1, r2, r3, maxcount); getch(); } | |
| Категория: Заказ 07.03.08 | Добавил: solver (07.03.2008) | |
| Просмотров: 2137 |