#include #include #include #define PI 3.141592653589794 typedef struct pt {double x,y;} pt; typedef pt pta[100]; typedef struct ptl {pta A; int size;} ptl; int main (int argc, char **argv, char **envp); ptl rotate (ptl list, double Th); double Area (ptl list); double max (double x, double y); void MaxMin (ptl list); double max (double x, double y); double min (double x, double y); double angle (pt a, pt b); double len (pt a, pt b); double equal (pt i, pt j, pt k, pt l, double psi); int main (int argc, char **argv, char **envp) { ptl list; int i, ct = 1; stdin = fopen ("gifts.in","r"); stdout = fopen ("gifts.out","w"); while (1) { scanf ("%d",&list.size); if (list.size==0) break; for (i = 0; i < list.size; i++) scanf ("%lf %lf",&list.A[i].x, &list.A[i].y); printf ("Gift %d\n",ct++); MaxMin (list); } fclose (stdin); fclose (stdout); return EXIT_SUCCESS; } ptl rotate (ptl list, double Th) { ptl newlist; int i; newlist.size = list.size; for (i = 0; i < list.size; i++) { newlist.A[i].x = list.A[i].x*cos(Th) - list.A[i].y*sin(Th); newlist.A[i].y = list.A[i].x*sin(Th) + list.A[i].y*cos(Th); } return newlist; } double Area (ptl list) { double maxx, maxy, minx, miny; int i; maxx = minx = list.A[0].x; maxy = miny = list.A[0].y; for (i = 1; i < list.size; i++) { maxx = max (maxx,list.A[i].x); minx = min (minx,list.A[i].x); maxy = max (maxy,list.A[i].y); miny = min (miny,list.A[i].y); } return (maxx-minx)*(maxy-miny); } double max (double x, double y) { return x > y ? x : y; } double min (double x, double y) { return x < y ? x : y; } void MaxMin (ptl list) { double maxa, mina,a, psi; int i,j,k,l; ptl temp; maxa = mina = Area (list); for (i = 0; i < list.size-1; i++) for (j = i+1; j < list.size; j++) { temp = rotate (list,-angle(list.A[i],list.A[j])); for (k = 0; k < list.size-1; k++) { a = Area (rotate (temp,PI/2)); maxa = max (maxa, a); mina = min (mina, a); for (l = k+1; l < list.size; l++) { psi = angle (temp.A[k],temp.A[l]); a = Area (rotate (temp,PI-psi)); maxa = max (maxa, a); mina = min (mina, a); a = Area (rotate (temp,PI/4-psi/2)); maxa = max (maxa, a); mina = min (mina, a); a = Area (rotate (temp,equal (temp.A[i],temp.A[j],temp.A[k], temp.A[l],psi))); maxa = max (maxa, a); mina = min (mina, a); } } } printf ("Minimum area = %.3f\n",mina); printf ("Maximum area = %.3f\n\n",maxa); } double angle (pt a, pt b) { return atan2 (a.y-b.y,a.x-b.x); } double len (pt a, pt b) { return sqrt (pow (a.x-b.x,2)+ pow (a.y-b.y,2)); } double equal (pt i, pt j, pt k, pt l, double psi) { double l1 = len (i,j), l2 = len (k,l); return atan2 (l2*cos(psi)-l1,l2*sin(psi)); }