Untitled
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...