Wednesday, October 5, 2011

 Algorithm:There are 2 possible arrangements for maximum size of 4-squares for a given size of paper
X X
X X

AND

X X X X

Thus, we get the formula:
let l = longer side of the rectangular paper
let s = shorter side of the rectangular paper
max square size = MAX(MIN(l/4.0, s), s/2.0)

Iterate through the answer and search for the first maximum.




Code:


#include<stdio.h>

#define MAX(a,b) (((a) > (b)) ? (a) : (b))

#define MIN(a,b) (((a) < (b)) ? (a) : (b))

int main(){

int i,n,num;

float l,s,tmp,size,mmm;



while(scanf("%d",&n)&&n){

mmm=0;

for(i=1;i<=n;i  ){

scanf("%f %f",&l,&s);

if(l<s) {

tmp=l;

l=s;

s=tmp;

}

size= MAX(MIN(l/4, s), s/2);

if(size>mmm) {mmm=size;num=i;}







}

printf("%d\n",num);





}

return 0;

}

No comments:

Post a Comment