hull.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 #define MAX 20000
   5
   6 struct pt { int x, y; char c; };
   7
   8 struct pt pt[MAX];
   9 int N;
  10 typedef long long int ll;
  11 struct pt up[MAX], down[MAX];
  12 int Nu, Nd;
  13
  14 int cmp(const void *X, const void *Y)
  15 {
  16         const struct pt *x = X, *y = Y;
  17         if (x->x < y->x)
  18                 return -1;
  19         if (x->x > y->x)
  20                 return 1;
  21         return 0;
  22 }
  23
  24 ll sign(ll ax, ll ay, ll bx, ll by)
  25 {
  26         return ax*by - ay*bx;
  27 }
  28
  29 int main(void)
  30 {
  31         N=0;
  32         while (scanf("%d %d '%c'", &pt[N].x, &pt[N].y, &pt[N].c) == 3) {
  33                 //pt[N].y -= 4000000; pt[N].x -= 4000000;
  34                 N++;
  35         }
  36         qsort(pt, N, sizeof(pt[0]), cmp);
  37         //for (int i=0; i<N; i++) printf("%d %d %c\n", pt[i].x, pt[i].y, pt[i].c);
  38         //printf("%d\n", (int) sign(-2,1,2,0));
  39         //printf("%d\n", (int) sign(-2,-1,2,0));
  40
  41         Nu = Nd = 1;
  42         up[0] = down[0] = pt[0];
  43         for (int i=1; i<N; i++) {
  44                 while (Nu > 1 && sign(up[Nu-2].x - up[Nu-1].x, up[Nu-2].y - up[Nu-1].y,
  45                               pt[i].x    - up[Nu-1].x, pt[i].y    - up[Nu-1].y) < 0)
  46                 Nu--;
  47                 up[Nu++] = pt[i];
  48                 while (Nd > 1 && sign(down[Nd-2].x - down[Nd-1].x, down[Nd-2].y - down[Nd-1].y,
  49                                       pt[i].x      - down[Nd-1].x, pt[i].y      - down[Nd-1].y) > 0)
  50                         Nd--;
  51                 down[Nd++] = pt[i];
  52         }
  53
  54         printf("### Upper hull:\n");
  55         for (int i=0; i<Nu; i++)
  56                 printf("%7d %7d '%c'\n", up[i].x, up[i].y, up[i].c);
  57         printf("### Lower hull:\n");
  58         for (int i=0; i<Nd; i++)
  59                 printf("%7d %7d '%c'\n", down[i].x, down[i].y, down[i].c);
  60
  61         return 0;
  62 }