POJ_1177

    这个题目和POJ_1151基本思路是一样的，一些具体的思路可以参考我的那篇题解：。

    相比算面积不同的是，每次计算面积的操作需要改为计算周长的操作，同时周长可以分成平行于x轴的部分和平行y轴的部分分开来求。

#include
     
       #include
      
        #include
       
         #define zero 1e-8 #define MAXD 10010 #define INF 10010 int N, X, M; struct square {
   double x1, y1, x2, y2; }s[MAXD]; double left[MAXD], right[MAXD], tx[MAXD], ty[MAXD]; int cmp1(const void *_p, const void *_q) {
       square *p = (square *)_p, *q = (square *)_q; return p->y1 < q->y1 ? -1 : 1; } int cmp2(const void *_p, const void *_q) {
       square *p = (square *)_p, *q = (square *)_q; return p->x1 < q->x1 ? -1 : 1; } int cmp3(const void *_p, const void *_q) {
   double *p = (double *)_p, *q = (double *)_q; return *p < *q ? -1 : 1; } double fabs(double x) {
   return x < 0 ? -x : x; } int dcmp(double x) {
   return fabs(x) < zero ? 0 : (x < 0 ? -1 : 1); } void init() {
   int i, j, k;     X = 0; for(i = 0; i < N; i ++)     {
           scanf("%lf%lf%lf%lf", &s[i].x1, &s[i].y1, &s[i].x2, &s[i].y2);         tx[X] = s[i].x1, ty[X] = s[i].y1;         ++ X;         tx[X] = s[i].x2, ty[X] = s[i].y2;         ++ X;     } } void solve() {
   int i, j, k; double ans = 0, up, down;     qsort(s, N, sizeof(s[0]), cmp1);     qsort(tx, X, sizeof(tx[0]), cmp3);     M = 0; for(i = 1; i < X; i ++) if(dcmp(tx[i] - tx[i - 1]) != 0)         {
               left[M] = tx[i - 1], right[M] = tx[i];             ++ M;         } for(i = 0; i < M; i ++)     {
           up = down = -INF; for(j = 0; j < N; j ++) if(dcmp(left[i] - s[j].x1) >= 0 && dcmp(right[i] - s[j].x2) <= 0)             {
   if(dcmp(s[j].y1 - up) > 0)                 {
                       ans += 2 * (right[i] - left[i]);                     down = s[j].y1, up = s[j].y2;                 } else if(dcmp(s[j].y2 - up) > 0)                     up = s[j].y2;             }     }     qsort(s, N, sizeof(s[0]), cmp2);     qsort(ty, X, sizeof(ty[0]), cmp3);     M = 0; for(i = 1; i < X; i ++) if(dcmp(ty[i] - ty[i - 1]) != 0)         {
               left[M] = ty[i - 1], right[M] = ty[i];             ++ M;         } for(i = 0; i < M; i ++)     {
           up = down = -INF; for(j = 0; j < N; j ++) if(dcmp(left[i] - s[j].y1) >= 0 && dcmp(right[i] - s[j].y2) <= 0)             {
   if(dcmp(s[j].x1 - up) > 0)                 {
                       ans += 2 * (right[i] - left[i]);                     down = s[j].x1, up = s[j].x2;                 } else if(dcmp(s[j].x2 - up) > 0)                     up = s[j].x2;             }     }     printf("%.0lf\n", ans); } int main() {
   while(scanf("%d", &N) == 1)     {
           init();         solve();     } return 0; }