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 » Sun Sep 19, 2010 11:39 pm

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 » Mon Sep 20, 2010 1:07 pm

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 » Mon Sep 20, 2010 1:47 pm


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

Re: 11834 - Elevator

Post by LifeMaker » Mon Sep 20, 2010 2:00 pm

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 » Mon Sep 20, 2010 3:22 pm

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 » Mon Sep 20, 2010 4:37 pm

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 » Wed Dec 28, 2011 7:36 am

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.

User avatar
lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

11834 - Elevator

Post by lnr » Thu Apr 10, 2014 4:53 am

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 » Thu Apr 10, 2014 8:51 pm

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!

User avatar
lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re: 11834 - Elevator

Post by lnr » Fri Apr 11, 2014 5:26 am

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 » Fri Apr 11, 2014 10:52 pm

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!

User avatar
lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re: 11834 - Elevator

Post by lnr » Sat Apr 12, 2014 5:04 am

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)”