11834 - Elevator

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11834 - Elevator

Post by LifeMaker »

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;
}
thanks in advance

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

Re: 11834 - Elevator

Post by krien »

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

Post by pdwd »


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

Re: 11834 - Elevator

Post by LifeMaker »

sorry pdwd, but i didn't understand what ctgPi said :oops: 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

Post by krien »

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

Post by LifeMaker »

thanks a lot krien, i got it now :)

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

Re: 11834 - Elevator

Post by shrabanti »

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: 142
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

11834 - Elevator

Post by lnr »

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);
    int L,C,R1,R2,sum_of_radi,min;
    double angle_line;
    while(scanf("%d %d %d %d",&L,&C,&R1,&R2)) {
        if(L+C+R1+R2==0)
            break;
        sum_of_radi=R1+R2;
        if(R1<R2){
            min=R1;
        } else {
            min=R2;
        }
        angle_line=(int)sqrt((R1*R1)+(R2*R2));
        if(sum_of_radi<min && sum_of_radi<angle_line) {
            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

Post by brianfry713 »

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: 142
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re: 11834 - Elevator

Post by lnr »

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

Post by brianfry713 »

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: 142
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re: 11834 - Elevator

Post by lnr »

brianfry713 wrote:http://apps.topcoder.com/forums/?module ... 66&start=0
Try solving it without using floating point.
I am still not understanding the case of 45 degree. Can you please explain more with picture/figure/photo ? And where i am doing the mistake in code?

Post Reply

Return to “Volume 118 (11800-11899)”