/* mwt.c Compute the minimum weight triangulation of convex polygons begun: August 15, 2006 by: Steven Skiena */ /* Copyright 2003 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. This program appears in my book: "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information. This book can be ordered from Amazon.com at http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include "bool.h" #include "geometry.h" #include point first_point; /* first hull point */ convex_hull(point in[], int n, polygon *hull) { int i; /* input counter */ int top; /* current hull size */ bool smaller_angle(); if (n <= 3) { /* all points on hull! */ for (i=0; ip[i]); hull->n = n; return; } sort_and_remove_duplicates(in,&n); copy_point(in[0],&first_point); qsort(&in[1], n-1, sizeof(point), smaller_angle); copy_point(first_point,hull->p[0]); copy_point(in[1],hull->p[1]); copy_point(first_point,in[n]); /* sentinel to avoid special case */ top = 1; i = 2; while (i <= n) { if (!ccw(hull->p[top-1], hull->p[top], in[i])) top = top-1; /* top not on hull */ else { top = top+1; copy_point(in[i],hull->p[top]); i = i+1; } } hull->n = top; } sort_and_remove_duplicates(point in[], int *n) { int i; /* counter */ int oldn; /* number of points before deletion */ int hole; /* index marked for potential deletion */ bool leftlower(); qsort(in, *n, sizeof(point), leftlower); oldn = *n; hole = 1; for (i=1; in); i++) t[i][i]=0; /* initialize DP table */ for (gap=1; gap<=(p->n); gap++) for (i=1; i<=n-gap; i++) { j = i+gap; t[i][j] = INFINITY; f main(){ point in[MAXPOLY]; /* input points */ polygon hull; /* convex hull */ int n; /* number of points */ int i; /* counter */ scanf("%d",&n); for (i=0; i (*p2)[X]) return (1); if ((*p1)[Y] < (*p2)[Y]) return (-1); if ((*p1)[Y] > (*p2)[Y]) return (1); return(0); } /* bool leftlower(point *p1, point *p2) { if (fabs((*p1)[X] - (*p2)[X]) > EPSILON) { if ((*p1)[X] < (*p2)[X]) return (-1); if ((*p1)[X] > (*p2)[X]) return (1); } if (fabs((*p1)[Y] - (*p2)[Y]) > EPSILON) { if ((*p1)[Y] < (*p2)[Y]) return (-1); if ((*p1)[Y] > (*p2)[Y]) return (1); } return(0); } */ bool smaller_angle(point *p1, point *p2) { if (collinear(first_point,*p1,*p2)) { if (distance(first_point,*p1) <= distance(first_point,*p2)) return(-1); else return(1); } if (ccw(first_point,*p1,*p2)) return(-1); else return(1); }