Из множества выбрать три различные точки по условию - 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;
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

8   голосов , оценка 4.125 из 5
Похожие ответы