C
Well this one got me stumped for a bit but after a few false starts, lots of debugging and some cleanup I'd say I have a pretty good solution now! The points being tiles rather than zero-width corners was the tricky bit here.
Basic working: it walks through the points, keeping track of normal vectors (the "outside" direction). With those, it generates the zero-width outline around the points, and from there on it's pretty much old fashioned line intersection checks.
The initial nasty solve took 1.2 seconds on my Raspberry Pi 400, but some optimization (like sorting the edges list) brought that down to 0.08s on the Pi, and 0.02s on my 10-year old PC, and I'm quite happy with the code now.
Code
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <inttypes.h>
#include <assert.h>
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define LEN(a) (sizeof(a)/sizeof(*(a)))
#define MAXP 512
/*
* There are two main problems with part 2:
* 1. Deciding what is inside and what is outside of the polyline
* 2. The points being _tiles_, not zero-width coordinates
*
* This solution walks the outline and calculates "normals" for each
* point, which are angles pointing _out_ of the shape. Those are used
* to derrive the outside boundary of the shape, the lines that go
* around, not through, the corner tiles. Witth that we can do
* more-or-less normal intersection checks.
*
* Angles are stored as 1/8ths of a circle.
*/
struct point { int x,y; };
struct edge { int off, lo,hi; };
static struct point pts[MAXP];
static struct edge hedges[MAXP/2];
static struct edge vedges[MAXP/2];
static int norms[MAXP];
static int np, nhe, nve;
static int wrapa(int a) { return (a+8)%8; }
static int
cmp_edges(const void *a, const void *b)
{
return ((const struct edge *)a)->off -
((const struct edge *)b)->off;
}
static int
line_dir(struct point a, struct point b)
{
return 4*(a.x>b.x || a.y<b.y) + 2*(a.x!=b.x);
}
static void
calculate_normals(void)
{
int i, dir1,dir2, angle;
int normal; /* relative to the current line */
dir1 = line_dir(pts[np-1], pts[0]);
normal = wrapa(dir1 - 2); /* start left, assuming CCW order */
for (i=0; i<np; i++) {
dir2 = line_dir(pts[i], pts[i==np-1 ? 0 : i+1]);
angle = dir2 == dir1-2 || dir2 == dir1+6 ? -2 : 2;
/* the point's normal is diagonal, halfway turned */
norms[i] = wrapa(normal + angle/2);
dir1 = dir2;
normal = wrapa(normal + angle);
}
}
static void
generate_edges(void)
{
struct point a,b;
int i,j;
for (i=0; i<np; i++) {
a = pts[i];
b = pts[(j = i==np-1 ? 0 : i+1)];
/* shift the line to be _around_ point */
a.x += norms[i]<4; a.y += norms[i]>2 && norms[i]<6;
b.x += norms[j]<4; b.y += norms[j]>2 && norms[j]<6;
if (a.x == b.x) {
assert(nve < (int)LEN(vedges));
vedges[nve].off = a.x;
vedges[nve].lo = MIN(a.y, b.y);
vedges[nve].hi = MAX(a.y, b.y);
nve++;
} else if (a.y == b.y) {
assert(nhe < (int)LEN(hedges));
hedges[nhe].off = a.y;
hedges[nhe].lo = MIN(a.x, b.x);
hedges[nhe].hi = MAX(a.x, b.x);
nhe++;
} else
assert(!"diagonal line");
}
qsort(hedges, nhe, sizeof(*hedges), cmp_edges);
qsort(vedges, nve, sizeof(*vedges), cmp_edges);
}
static bool
rect_inside(struct point a, struct point b)
{
struct edge *e;
int x0,y0,x1,y1;
/*
* Line intersection of the four rectangle edges against all
* the polyline edges, with a caveat: the outline is 1 unit
* thick, not zero-width! This is why some of the comparisons
* are or-equals.
*/
x0 = MIN(a.x, b.x); y0 = MIN(a.y, b.y);
x1 = MAX(a.x, b.x); y1 = MAX(a.y, b.y);
for (e = vedges; e < vedges+nve; e++) {
if (e->off <= x0) continue;
if (e->off > x1) break;
if (y0 >= e->lo && y0 < e->hi) return false;
if (y1 >= e->lo && y1 < e->hi) return false;
}
for (e = hedges; e < hedges+nhe; e++) {
if (e->off <= y0) continue;
if (e->off > y1) break;
if (x0 >= e->lo && x0 < e->hi) return false;
if (x1 >= e->lo && x1 < e->hi) return false;
}
return true;
}
int
main()
{
int64_t p1=0,p2=0, area, i,j;
for (; scanf(" %d,%d", &pts[np].x, &pts[np].y)==2; np++)
assert(np+1 < MAXP);
assert(np >= 4);
calculate_normals();
generate_edges();
for (i=0; i<np-1; i++)
for (j=i+1; j<np; j++) {
area = (int64_t)(abs(pts[i].x - pts[j].x) + 1) *
(int64_t)(abs(pts[i].y - pts[j].y) + 1);
if (area > p1)
p1 = area;
if (area > p2 && rect_inside(pts[i], pts[j]))
p2 = area;
}
printf("09: %"PRIi64" %"PRIi64"\n", p1, p2);
}