Из множества выбрать три различные точки по условию - C (СИ)
Формулировка задачи:
Даны два множества точек на плоскости. Из первого множества выбрать три различные точки так, чтобы треугольник с вершинами в этих точках содержал внутри себя максимальное количество точек второго множество
Решение задачи: «Из множества выбрать три различные точки по условию»
textual
Листинг программы
#include <stdio.h> #include <stdlib.h> typedef struct tag_point { int x; int y; } Point; Point *fiSet; Point *seSet; int Q(int ax, int ay, int bx, int by, int atx, int aty) { return atx * (by - ay) + aty * (ax - bx) + ay * bx - ax * by; } int Check(int aAx, int aAy, int aBx, int aBy, int aCx, int aCy, int aPx, int aPy) { int q1 = Q(aAx, aAy, aBx, aBy, aPx, aPy); int q2 = Q(aBx, aBy, aCx, aCy, aPx, aPy); int q3 = Q(aCx, aCy, aAx, aAy, aPx, aPy); if ( ((q1 >= 0) && (q2 >= 0) && (q3 >= 0)) || ((q1 < 0) && (q2 < 0) && (q3 < 0)) ) return 1; else return 0; } int main() { int n, m, i, j, k, x, y, g, l; scanf("%d", &n); //n - число точек в первом множестве scanf("%d", &m); //m - число точек во втором множестве fiSet = (Point*)malloc(sizeof(Point) * n); seSet = (Point*)malloc(sizeof(Point) * m); for(i = 0; i < n; i++) { scanf("%d", &x); scanf("%d", &y); fiSet[i].x = x; fiSet[i].y = y; } for(i = 0; i < m; i++) { scanf("%d", &x); scanf("%d", &y); seSet[i].x = x; seSet[i].y = y; } Point p[3]; int iHavePoints = -1; for(i = 0; i < n; ++i) for(j = i + 1; j < n; ++j) for(k = j + 1; k < n; ++k) { g = 0; for(l = 0; l < m; l++) g += Check(fiSet[i].x, fiSet[i].y, fiSet[j].x, fiSet[j].y, fiSet[k].x, fiSet[k].y, seSet[l].x, seSet[l].y); if(g > iHavePoints) { iHavePoints = g; p[0].x = fiSet[i].x; p[0].y = fiSet[i].y; p[1].x = fiSet[j].x; p[1].y = fiSet[j].y; p[2].x = fiSet[k].x; p[2].y = fiSet[k].y; } } //Выводим три искомые точки printf("%d %d\n", p[0].x, p[0].y); printf("%d %d\n", p[1].x, p[1].y); printf("%d %d\n", p[2].x, p[2].y); free(fiSet); free(seSet); return 0; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д