UVa : 10703 (Free spots)


Title : Free spots

Link : http://uva.onlinejudge.org/external/107/10703.html

Tricky Lines :

  1. Follow then N lines, composed of four integers X1, Y1, X2, Y2, such that (X1, Y1) and (X2, Y2) are the positions of two opposite corners of a sub-board.
  2. Output format.

Analysis :

  1. make a board and initialize it with false
  2. mark every sub-rectangle true and then count

Runtime : 0.016s

Critical input : 
15 10 3
3 3 7 1
7 8 3 6
7 11 3 13

0 0 0

Critical Output :
There are 120 empty spots.

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

bool a [500 + 5] [500 + 5];
int X1, Y1, X2, Y2;

void make_consistent ()
{
    if ( X1 > X2 && Y1 <= Y2 ) swap (X1, X2);

    else if ( X1 >= X2 && Y1 >= Y2 ) {
        swap (X1, X2);
        swap (Y1, Y2);
    }

    else if ( X1 <= X2 && Y1 > Y2 ) swap (Y1, Y2);
}

void reset ()
{
    for ( int i = 0; i < 505; i++ ) memset (a [i], false, sizeof (a [i]));
}

int main ()
{
    int w, h, n;

    while ( scanf ("%d %d %d", &w, &h, &n) ) {
        if ( w == 0 && h == 0 && n == 0 ) break;

        reset ();

        for ( int i = 0; i < n; i++ ) {
            scanf ("%d %d %d %d", &X1, &Y1, &X2, &Y2);
            make_consistent ();

            for ( int j = X1; j <= X2; j++ ) {
                for ( int k = Y1; k <= Y2; k++ ) a [j] [k] = true;
            }

        }

        int res = 0;

        for ( int i = 1; i <= w; i++ ) {
            for ( int j = 1; j <= h; j++ ) if ( a [i] [j] == false ) res++;
        }


        if ( res == 0 ) printf ("There is no empty spots.\n");
        else if ( res == 1 ) printf ("There is one empty spot.\n");
        else printf ("There are %d empty spots.\n", res);
    }

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s