167 lines
3.7 KiB
C
167 lines
3.7 KiB
C
/* ************************************************************************** */
|
|
/* */
|
|
/* ::: :::::::: */
|
|
/* part2.c :+: :+: :+: */
|
|
/* +:+ +:+ +:+ */
|
|
/* By: tomoron <tomoron@student.42.fr> +#+ +:+ +#+ */
|
|
/* +#+#+#+#+#+ +#+ */
|
|
/* Created: 2024/07/17 23:03:36 by tomoron #+# #+# */
|
|
/* Updated: 2025/12/10 15:08:17 by tomoron ### ########.fr */
|
|
/* */
|
|
/* ************************************************************************** */
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <math.h>
|
|
#include "libft/libft.h"
|
|
|
|
typedef struct s_cords
|
|
{
|
|
double x;
|
|
double y;
|
|
} t_coords;
|
|
|
|
static t_coords parse_line(char *line)
|
|
{
|
|
t_coords res;
|
|
|
|
res.x = atoi(line);
|
|
while(ft_isdigit(*line))
|
|
line++;
|
|
line++;
|
|
res.y = atoi(line);
|
|
return(res);
|
|
}
|
|
|
|
static int is_point_on_line(t_coords pos, t_coords a, t_coords b)
|
|
{
|
|
double cross = (pos.x - a.x) * (b.y - a.y) - (pos.y - a.y) * (b.x - a.x);
|
|
if(cross != 0)
|
|
return(0);
|
|
return(pos.x >= fmin(a.x, b.x) && pos.x <= fmax(a.x, b.x) &&
|
|
pos.y >= fmin(a.y, b.y) && pos.y <= fmax(a.y, b.y));
|
|
|
|
}
|
|
|
|
|
|
static int is_point_in_poly(t_coords pos, t_coords *poly, int len)
|
|
{
|
|
int inside;
|
|
int i;
|
|
t_coords cur[2];
|
|
double intersect;
|
|
|
|
inside = 0;
|
|
i = 0;
|
|
while(i < len)
|
|
{
|
|
cur[0] = poly[i];
|
|
cur[1] = poly[(i + 1) % len];
|
|
|
|
if(is_point_on_line(pos, cur[0], cur[1]))
|
|
{
|
|
inside = 1;
|
|
break;
|
|
}
|
|
|
|
if((cur[0].y > pos.y) != (cur[1].y > pos.y))
|
|
{
|
|
intersect = ((cur[1].x - cur[0].x) * (pos.y - cur[0].y)) / (cur[1].y - cur[0].y) + cur[0].x;
|
|
if(pos.x < intersect)
|
|
inside = !inside;
|
|
}
|
|
i++;
|
|
}
|
|
return(inside);
|
|
}
|
|
|
|
static int is_line_in_poly(t_coords p1, t_coords p2, t_coords *poly, int len)
|
|
{
|
|
t_coords from;
|
|
t_coords to;
|
|
|
|
from.x = fmin(p1.x, p2.x);
|
|
from.y = fmin(p1.y, p2.y);
|
|
to.x = fmax(p1.x, p2.x);
|
|
to.y = fmax(p1.y, p2.y);
|
|
|
|
while(from.x <= to.x && from.y <= to.y)
|
|
{
|
|
if(!is_point_in_poly(from, poly, len))
|
|
{
|
|
return(0);
|
|
}
|
|
if(from.x != to.x)
|
|
from.x++;
|
|
else
|
|
from.y++;
|
|
}
|
|
return(1);
|
|
}
|
|
|
|
static int is_all_in_poly(t_coords p1, t_coords p2, t_coords *poly, int len)
|
|
{
|
|
|
|
if(!is_line_in_poly(p1,(t_coords){p2.x, p1.y}, poly, len) ||
|
|
!is_line_in_poly((t_coords){p2.x, p1.y}, p2, poly, len) ||
|
|
!is_line_in_poly(p2, (t_coords){p1.x, p2.y}, poly, len) ||
|
|
!is_line_in_poly((t_coords){p1.x, p2.y},p1, poly, len))
|
|
return(0);
|
|
return(1);
|
|
}
|
|
|
|
static long int get_biggest_area(t_coords *co, int len)
|
|
{
|
|
int i;
|
|
int j;
|
|
long int max;
|
|
long int tmp;
|
|
|
|
i = 0;
|
|
max = 0;
|
|
while(i < len)
|
|
{
|
|
j = i;
|
|
while(++j < len)
|
|
{
|
|
if(i == j)
|
|
continue;
|
|
tmp = ((long)fabs(co[i].x - co[j].x) + 1) * ((long)fabs(co[i].y - co[j].y) + 1);
|
|
if(tmp <= max)
|
|
continue;
|
|
if(!is_point_in_poly((t_coords){co[i].x,co[j].y}, co, len) || !is_point_in_poly((t_coords){co[j].x,co[i].y}, co, len))
|
|
continue;
|
|
if(!is_all_in_poly(co[i], co[j], co, len))
|
|
continue;
|
|
printf("got %ld for %.0f, %.0f to %.0f, %.0f checking points \n", tmp, co[i].x, co[i].y, co[j].x, co[j].y);
|
|
max = tmp;
|
|
}
|
|
i++;
|
|
}
|
|
return(max);
|
|
}
|
|
|
|
long int resolve_part2(char *input, char **split)
|
|
{
|
|
(void)input;
|
|
int len;
|
|
t_coords *co;
|
|
int i;
|
|
|
|
len = 0;
|
|
while(split[len])
|
|
len++;
|
|
co = malloc(len * sizeof(t_coords));
|
|
i = 0;
|
|
while(split[i])
|
|
{
|
|
co[i] = parse_line(split[i]);
|
|
i++;
|
|
}
|
|
return(get_biggest_area(co, len));
|
|
}
|
|
// 4604141472 >
|
|
// 4604141472 :/
|
|
// 4501110590 >
|
|
// 1588990708
|