Page 1 of 1

11834 - Elevator

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

Re: 11834 - Elevator

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

Re: 11834 - Elevator

Posted: Mon Sep 20, 2010 1:47 pm
by pdwd

Re: 11834 - Elevator

Posted: Mon Sep 20, 2010 2:00 pm
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 :-?

Re: 11834 - Elevator

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

Re: 11834 - Elevator

Posted: Mon Sep 20, 2010 4:37 pm
by LifeMaker
thanks a lot krien, i got it now :)

Re: 11834 - Elevator

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

11834 - Elevator

Posted: Thu Apr 10, 2014 4:53 am
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)

Re: 11834 - Elevator

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

Re: 11834 - Elevator

Posted: Fri Apr 11, 2014 5:26 am
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?

Re: 11834 - Elevator

Posted: Fri Apr 11, 2014 10:52 pm
by brianfry713
http://apps.topcoder.com/forums/?module ... 66&start=0
Try solving it without using floating point.

Re: 11834 - Elevator

Posted: Sat Apr 12, 2014 5:04 am
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?