Untitled

 avatar
unknown
plain_text
2 years ago
4.0 kB
4
Indexable
#include <stdio.h>
#include <stdlib.h>

// definindo a estrutura de um ponto (x, y)
typedef struct {
    int x;
    int y;
} Ponto;

// função para comparar dois pontos pela coordenada x
int cmpPontos(const void* p1, const void* p2) {
    Ponto *a = (Ponto*) p1;
    Ponto *b = (Ponto*) p2;
    if (a->x < b->x) return -1;
    if (a->x > b->x) return 1;
    return 0;
}

int main() {
    int n, xa, xb;
    scanf("%d %d %d", &n, &xa, &xb);
    
    // alocando dinamicamente um array de pontos
    Ponto* pontos = malloc(n * sizeof(Ponto));

    // lendo os pontos
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &pontos[i].x, &pontos[i].y);
    }

    // ordenando os pontos pela coordenada x
    qsort(pontos, n, sizeof(Ponto), cmpPontos);

    int ans = 0;
    // percorrendo os pontos da esquerda para a direita
    for (int i = 0; i < n; i++) {
        // se o ponto i não estiver entre as âncoras, ignore
        if (pontos[i].x <= xa || pontos[i].x >= xb) continue;

        // definindo o ponto A como a âncora mais próxima à esquerda
        Ponto a = {xa, 0};
        // definindo o ponto B como a âncora mais próxima à direita
        Ponto b = {xb, 0};

        // percorrendo os pontos da esquerda para a direita
        // em busca do ponto mais alto que pode ser ligado com o ponto i
        for (int j = 0; j < n; j++) {
            // se o ponto j estiver à esquerda do ponto i ou não puder ser ligado a ele, ignore
            if (pontos[j].x < pontos[i].x || pontos[j].x > xb) continue;
            // se o ponto j estiver acima do ponto i e puder ser ligado a ele, defina-o como ponto C
            if (pontos[j].y > pontos[i].y &&
                ((long long) (pontos[i].x - xa) * (pontos[j].y - 0)) ==
                ((long long) (pontos[j].x - pontos[i].x) * (pontos[i].y - 0))) {
                Ponto c = {pontos[j].x, pontos[j].y};
                // verificando se o segmento (i, c) intersecta o segmento (a, b)
                int flag = 1;
                for (int k = 0; k < n; k++) {
                    if (pontos[k].x <= xa || pontos[k].x >= xb) continue;
                    if (pontos[k].x > pontos[i].x && pontos[k].x < pontos[j].x) {
                        if (((long long) (pontos[k].x - pontos[i].x) * (c.y - pontos[i].y)) >
                           for (int i = 0; i < n; i++) {
        scanf("%d%d", &pontos[i].x, &pontos[i].y);
    }
    qsort(pontos, n, sizeof(ponto), comp); // ordena o vetor de pontos pela coordenada x
    int max_ligados = 0;
    for (int i = 0; i < n; i++) { // para cada ponto i
        for (int j = i + 1; j < n; j++) { // e para cada ponto j maior que i
            int ligados = 2; // inicializa o contador de pontos ligados em 2, pois já estamos considerando os pontos i e j
            double xi = pontos[i].x, xj = pontos[j].x, yi = pontos[i].y, yj = pontos[j].y;
            for (int k = i + 1; k < j; k++) { // verifica quantos pontos podem ser ligados usando os pontos i e j
                double xk = pontos[k].x, yk = pontos[k].y;
                if ((yk - yi) * (xj - xi) == (yj - yk) * (xi - xk)) {
                    // se o ponto k pode ser ligado, atualiza o contador de pontos ligados
                    ligados++;
                }
            }
            // verifica se o número de pontos ligados usando os pontos i e j é maior que o número máximo já encontrado
            if (ligados > max_ligados) {
                // verifica se a interseção dos segmentos i-k e j-l não ocorre fora das âncoras
                if ((pontos[i].x <= pontos[j].x && pontos[j].x <= pontos[i].x + xb - xa) || (pontos[i].x >= pontos[j].x && pontos[i].x <= pontos[j].x + xb - xa)) {
                    // atualiza o número máximo de pontos ligados
                    max_ligados = ligados;
                }
            }
        }
    }
    printf("%d\n", max_ligados);
    free(pontos); // libera a memória alocada
    return 0;
}
Editor is loading...