La scala

di

Un gradino è un rettangolo che giace sul piano cartesiano, i cui lati sono paralleli ai due assi.
Una scala è una sequenza di gradini con le seguenti proprietà:

  • i lati inferiori di tutti i gradini giacciono sull’asse X;
  • il lato sinistro del primo gradino giace sull’asse Y;
  • il lato sinistro di ogni gradino successivo al primo giace sul lato destro del gradino precedente;
  • le altezze dei gradini sono strettamente decrescenti.

oii_2003_scala1La figura a destra mostra una scala.

Supponete di avere un insieme di punti sul piano cartesiano le cui coordinate sono numeri interi positivi.
Il vostro obiettivo è di trovare una scala tale che tutti i punti dell’insieme giacciano nell’area sottesa alla scala (oppure, sul bordo della scala stessa).
Fra tutte le scale possibili, volete sceglierne una che minimizzi l’area sottesa.

Dati in input

Il programma legge dati da un file di nome input.txt.

  • Sulla prima riga del file è indicato un singolo numero intero N che è il numero di punti.
  • Su ciascuna delle successive N righe è indicato un punto, espresso attraverso le sue coordinate (due numeri interi separati da uno spazio).

Dati in output

Il programma deve produrre un file di nome output.txt.
Questo file sarà costituito da una singola riga, contenente un singolo numero intero, che rappresenta l’area minima possibile di una scala che contenga tutti i punti.

Assunzioni

  • 1 ≤ N ≤ 10000.

oii_2003_scala2Esempi di input/output

input.txt output.txt
11
3 13
6 4
16 3
6 8
9 2
10 11
12 7
7 13
20 5
1 7
22 1		 180

La figura a destra mostra i punti e una scala di area minima che li contiene tutti.
Dalla figura l’area sottesa misura

7×13+3×11+2×7+8×5+2×1 = 91+33+14+40+2 = 180.

/*
    www.valcon.it    
    OII 2003 - Fase nazionale - LA SCALA
*/

#include 
#include 
#define NMAX 10000

typedef struct punto { int x, y; } PUNTO;

PUNTO punti[NMAX];

int cmp(const void *a, const void *b)
{
  PUNTO p1=*((PUNTO*)a);
  PUNTO p2=*((PUNTO*)b);

  if(p2.y != p1.y)          
     return (p2.y-p1.y);    /* ordinate decrescenti */
  else
     return (p2.x-p1.x);    /* se ordinate uguali, ascisse decrescenti */
}

int main()
{	
    FILE* fin =fopen( "input.txt","r");
    FILE* fout=fopen("output.txt","w");   
 
 	int N;  
    fscanf(fin, "%d", &N);
    for(int i=0; i < N; i++)
        fscanf(fin, "%d%d", &(punti[i].x), &(punti[i].y));
    qsort(punti, N, sizeof(PUNTO), cmp);          

    long risposta=punti[0].x*punti[0].y;                  /* 1° RETTANGOLO */
    int  ultimo=0;  
    for(int i=1; i < N; i++)
    {
        if(punti[i].x > punti[ultimo].x)             /* SE SUCCESSIVO... */
        {
            risposta += punti[i].y*(punti[i].x-punti[ultimo].x);
            ultimo=i;
        }
    }
   
   fprintf(fout, "%ld", risposta);
   return 0;
}