§@ªÌ: kcwu (¤p¥ú¥ú) ¬ÝªO: Prob_Solve
¼ÐÃD: Re: ½Ð°Ý688...
®É¶¡: Thu Jan  6 22:40:30 2000

¡° ¤Þ­z¡mvgod (§Ú©ê©ê:P)¡n¤§»Ê¨¥¡G
: ¬Ý¤F¥ú¥ú688ªºcode...
: µoıÁÙ¯u¬O¯«©_...:P
: ¨S·Q¨ìCODE¨º»ò²³æ..
: ¦ý§¹¥þ¬Ý¤£À´´N¬O^^
: ¥ú¥ú¯à¸ÑÄÀ¤@¤U«ç»ò§@ªº¶Ü?
¨þ¨þ, ¨º code §Ú¬O§Û¨Óªº ^^;
¼g±o¤Ó´Î¤F...
688 ¬Oºâ­±¿n¤§¥æ¶°..
IOI'98 day2 ªº picture «h¬O¨D¥æ¶°¦hÃä§Îªº©Pªø
³oÃD§A¥i¥H¬Ý¤@¤U¤j·|´£¨Ñªº solution
¥H¤U¸`¿ý§Ú¨º®É¼gªº°Ñ¦Ò¸Ñµª

/*³oÃDºâ¬O¤µ¦~ IOI ¤»ÃD¤¤³ÌÃøªº¤@ÃD, §Ú¤Î¥t¥~¤T¦W¶¤¤Í³£¥uµª¹ï«e¨âµ§ test data
³o¸Ì©Ò¤Þ¥Îªººtºâªk»Pµ{¦¡³£¬O¤j·|´£¨Ñªº°Ñ¦Ò¸Ñµª, ¬ÛÃö¸ê®Æ½Ð¨£:
http://olympiads.win.tue.nl/ioi/ioi98/contest/picture
³oÃD¬OÄÝ©ó´X¦óºtºâªkªºÃD¥Ø, ÁöµM¥»ÃD¹ï©ó¨C¤@²Õ´ú¸Õ¸ê®Æ³£¥u¦³°ß¤@¸Ñ,
¦ý¸Ñªk¬Û·í¦hºØ, ¤j®a¦³¾÷·|¥i¥H¸ÕµÛ¼g¼g¬Ý¡C
¸Ñªk«Ü¦h, ¦b³oÃä§Ú´£¥X§Úı±o¥H«e¤ñ¸û¤Ö¨£ªººtºâªk:
¦b³o­Óºtºâªk¤¤, ¤£¥u¬O¿é¤Jªº¯x§Î­n³Q°Q½×, ¨â­Ó¯x§Î­«Å|ªº¥æ¶°, ¤]­nµø¬°¤@­Ó·s
ªº¯x§Î¡C³o»ò°µÁöµM¦³¥i¯à·|²£¥Í¦h¹F 2^n-1 ­Ó¯x§Î, ¦ý¤@¯ë¨Ó»¡, ³oºØ±¡§Î¨Ã¤£·|¤Ó
ÄY­«¡C
®Ú¾Ú±Æ®e­ì²z:
 ¡U S1 ¡å S2 ¡å S3 ¡å ... ¡å Sn ¡U
= ýÐSi - ýСUSi¡äSj¡U + ýСUSi¡äSj¡äSk¡U - ýСUSi¡äSj¡äSk¡äSl¡U+......
  + (-1)^(m+1)ýСUS1¡äS2¡ä....¡äSm¡U
  ¥þ³¡¯x§ÎÁp¶°ªºÁ`©Pªø
= ¨C­Ó¯x§Îªº©Pªø - ¥ô¨â¯x§Î¥æ¶°ªº©Pªø + ¥ô¤T¯x§Î¥æ¶°ªº©Pªø - .......
  + (-1)^(m+1)*¥þ³¡¯x§Î¥æ¶°¹Ï§Îªº©Pªø

¤SµL½×¦h¤Ö¯x§Îªº¥æ¶°, ³£±NÁÙ¬O¯x§Î, ¦]¦¹¥i¥H§Q¥ÎÃþ¦ü°ÊºA³Wµeªº¤âªk,
§Q¥Î k-1 ­Ó¯x§Îªº¥æ¶°±o¨ì k ­Ó¯x§Îªº¥æ¶°¡C               */
/* Author: Michel Wermelinger (mw@di.fct.unl.pt) */
#include <stdio.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) > (b) ? (b) : (a))

typedef struct {
  char sign;
  short int x, y, X, Y;
  /* sign 1,-1 ªí¥Ü©_©Î°¸¼Æ­Ó¯x§Îªº¥æ¶°,
     x,y,X,Y ªí¥Ü¯x§Î¥ª¤U»P¥k¤W¨¤ªº®y¼Ð */
} pict;

#define MAX_PICT 7000
/* ³Ì¦h´X¶ô¯x§Î(§t¥æ¶°ªº), ¶· 9*MAX_PICT bytes */
pict p[MAX_PICT];

void intersect (pict p1, pict p2, pict *p3) /* ±N p1,p2 ¨â¯x§Îªº¥æ¶°¦s©ó p3 */
{
  p3->x = max(p1.x, p2.x); p3->y = max(p1.y, p2.y);
  p3->X = min(p1.X, p2.X); p3->Y = min(p1.Y, p2.Y);
  p3->sign = -p1.sign * p2.sign;
}

int main (void)
{
  long perim = 0;
  int npf, npt = 0; /* ¤À§Oªí¥Ü¿é¤Jªº¯x§Î¼Æ»P­pºâ®É¹ê»Úªº¯x§Î¼Æ¶q */
  FILE *f;
  int i, j, k;

  if ((f = fopen("PICTURE.IN", "r")) == NULL) {
    printf("Empty file!\n");
    return 0;
  }

  fscanf (f, "%d\n", &npf);
  for (i = 0; i < npf ; i++) {
     k = npt++;
     fscanf(f, "%d %d %d %d\n", &p[k].x, &p[k].y, &p[k].X, &p[k].Y);
     p[k].sign = 1;
     for (j = 0;  j < k; j++)  {
       intersect  (p[j] , p[k] , &p[npt]);
       if ((p[npt].X > p[npt].x && p[npt].Y >= p[npt].y) ||
           (p[npt].X == p[npt].x && p[npt].Y > p[npt].y)) /* ·í p[npt] ¦s¦b */
         if (p[npt].x == p[k].x && p[npt].X == p[k].X &&
             p[npt].y == p[k].y && p[npt].Y == p[k].Y)  {
           npt = k;                    /* p[k] §¹¥þ³Q p[j] Âл\«h±Ë±ó p[k] */
           break;
         } else
           npt++;
     }
  }
  fclose(f);

  for (i = 0; i < npt; i++)
    perim += (long)p[i].sign * 2 * (p[i].X - p[i].x + p[i].Y - p[i].y);
  printf ("Perimeter=%ld\n", perim);
  f = fopen("PICTURE.OUT", "w");
  fprintf (f, "%ld\n", perim);
  fclose(f);
  return 0;
}