## 11834 - Elevator

Moderator: Board moderators

LifeMaker
New poster
Posts: 6
Joined: Sun Sep 19, 2010 11:28 pm

### 11834 - Elevator

Hi all,
i was trying to solve this problem "Elevator" from the Brazilian National Contest
http://uva.onlinejudge.org/index.php?op ... oblem=2934

my approach is to get the minimum diagonal of a rectangle to enclose the 2 circles, and if this diagonal is <= the diagonal of the elevator, then i print 'S', else i print 'N'. however this approach fails in the fourth sample test case and i can't think of any other approach. i also don't see how we can pack the 2 circles in the fourth test case :S

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <complex>
using namespace std;

#define epsilon 0.00000000001

int main(){
int h,w,r1,r2;
double needed, actual;
scanf("%d %d %d %d",&h,&w,&r1,&r2);
while(h||w||r1||r2){
needed = r1+hypot(r1,r1)+r2+hypot(r2,r2);
actual = hypot(h,w);
if(needed-actual < epsilon) printf("S\n");
else printf("N\n");
}
return 0;
}
``````

krien
New poster
Posts: 5
Joined: Mon Sep 20, 2010 12:51 pm

### Re: 11834 - Elevator

The diagonal is correct, but I think that it is better to find a way where you compare only integers.
Furthermore, You have to consider the possibility of include both circles in vertical or in horizontal.

pdwd
New poster
Posts: 19
Joined: Sat May 15, 2010 4:35 pm

### Re: 11834 - Elevator

LifeMaker
New poster
Posts: 6
Joined: Sun Sep 19, 2010 11:28 pm

### Re: 11834 - Elevator

sorry pdwd, but i didn't understand what ctgPi said i'd be really grateful if you could illustrate it more
and if this approach is totally wrong, what is the correct approach to this problem

krien
New poster
Posts: 5
Joined: Mon Sep 20, 2010 12:51 pm

### Re: 11834 - Elevator

It means that you have to put always a circle on a corner and the second one have to be connected with the first one.
Both circles have an angle with abscissa axis that goes from 0º to 90º and not always 45º as you consider.

SPOILER

You can delete r1+r2 of the width and r1+r2 of the height, and then calculate the diagonal of the final rectangle and check if it is bigger or equal than r1+r2.

LifeMaker
New poster
Posts: 6
Joined: Sun Sep 19, 2010 11:28 pm

### Re: 11834 - Elevator

thanks a lot krien, i got it now

shrabanti
New poster
Posts: 1
Joined: Wed Dec 28, 2011 7:29 am

### Re: 11834 - Elevator

Ya, it's not always 45º angle, Krien. I have connected the second one with the first.
You are the master my dear friend. Your suggestion worked. Learned a new thing today "Elevator".And sorry for opening an old thread again.

lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm

### 11834 - Elevator

Code: Select all

``````#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <iostream>

using namespace std;

int main(int argc, char** argv) {
//freopen("in.txt","r",stdin);
double angle_line;
while(scanf("%d %d %d %d",&L,&C,&R1,&R2)) {
if(L+C+R1+R2==0)
break;
if(R1<R2){
min=R1;
} else {
min=R2;
}
angle_line=(int)sqrt((R1*R1)+(R2*R2));
printf("S\n");
} else {
printf("N\n");
}
}
return 0;
}
``````
Can anyone explain the cases of this problem? (the diagonal case)
Last edited by lnr on Sat Apr 12, 2014 5:03 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11834 - Elevator

Doesn't match the sample I/O.
See: http://acm.uva.es/board/viewtopic.php?t=50729
Try using double instead of float.
Check input and AC output for thousands of problems on uDebug!

lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm

### Re: 11834 - Elevator

brianfry713 wrote:Doesn't match the sample I/O.
See: http://acm.uva.es/board/viewtopic.php?t=50729
Try using double instead of float.
I have read that thread and re-read the problem, but could not understand it. Can you please explain more about the cases of the problem, specially the diagonal case with picutre?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11834 - Elevator

http://apps.topcoder.com/forums/?module ... 66&start=0
Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm