Page 1 of 1

10053 - Envelopes

Posted: Fri Jun 28, 2002 3:29 pm
by cyfra
Hi!

I am not sure whether I understand the task correctly....

Could you tell me whet is the output for this test case :
2 2
10 10
10 10
10 10 3
1 1 1
Thanks in advance :wink:

Posted: Fri Jun 28, 2002 8:30 pm
by gvcormac
[incorrect comment deleted]

10053

Posted: Tue Jan 07, 2003 3:59 am
by ram
I dont think I understood the problem correctly. Can anybody help me???

For this input:

2 4
105 9
99 149
110 10 10
100 50 5
150 100 7
90 140 15

How can the output be:
2
3

How can greeting with dimensions 105 9 fit into the envelope with dimensions 100 50. Does this make sense?????

And are there infinite number of envelopes of each given size????

Thanks for the help

Got the same question..

Posted: Wed Jan 08, 2003 11:23 am
by Whinii F.
I'm confused about it too. How can a card of dimension 105 x 9 fit in an envelope of size 100 x 50? Can the envelopes distorted?? What's the trick in this?

ps. ram, trying a search will notify you that there are infinite envelopes of each kind..

Posted: Wed Jan 08, 2003 9:45 pm
by Caesum
it will fit in diagonally

Oh!! @_@

Posted: Thu Jan 09, 2003 11:42 am
by Whinii F.
That was the way..

I was so silly :(

Posted: Mon Jul 07, 2003 4:01 am
by Whinii F.
Is there anybody who solved this problem by numerical method (i.e. binary searching) ?

I was around this problem for months and there seems to be no way to get me accepted using binary search. I tried everything I could think of and failed every way.

I attach my most recently written code using long doubles.. anybody got an advice please reply.

[c]#include <stdio.h>
#include <math.h>

#define INF 999999999
#define eps 0.000000001
#define abs(x) ((x) < 0 ? -(x) : (x))
#define equal(a, b) (abs((a)-(b)) < eps)

int m, n;
long double e_w[10], e_h[10], c_w[5], c_h[5];
long double pi = 2.0 * acos(0);
long double halfpi;
int e_c[10];

int fits(long double cw, long double ch, long double ew, long double eh)
{
long double l = 0.0, r = halfpi, m;
long double wp, hp;
if(cw < ew + eps)
{
l = r = 0.0;
}
else
{
/* meaningless */
if(ch > ew)
return 0;
while(1)
{
m = (l+r) * 0.5;
wp = cos(halfpi - m) * ch + cos(m) * cw;
if(equal(wp, ew))
break;
if(wp > ew)
l = m;
else
r = m;
}
}
m = (l+r) * 0.5;
wp = cos(halfpi - m) * ch + cos(m) * cw;
hp = sin(halfpi - m) * ch + sin(m) * cw;
return (wp <= ew + eps) && (hp <= eh + eps);
}

void solve(void)
{
int i, j, min;
int mincost;
for(i = 0; i < m; i++)
{
mincost = INF;
for(j = 0; j < n; j++)
{
if(e_c[j] < mincost && (fits(c_w, c_h, e_w[j], e_h[j])||fits(c_h, c_w, e_w[j], e_h[j])))
{
mincost = e_c[j];
min = j;
}
}
if(mincost == INF)
printf("cannot buy\n");
else
printf("%d\n", min+1);
}
}

int main(void)
{
int i, c = 0;
halfpi = pi * 0.5;
while(scanf("%d %d", &m, &n) == 2)
{
if(m == 0 && n == 0)
break;
for(i = 0; i < m; i++)
scanf("%llf %llf", &c_w, &c_h);
for(i = 0; i < n; i++)
scanf("%llf %llf %d", &e_w, &e_h, &e_c);
if(c++) printf("\n");
printf("Case #%d\n", c);
solve();
}
return 0;
}[/c]

Thanks in advance,

Posted: Fri Sep 05, 2003 4:42 am
by coolbila
one envelope can appear just one time

my AC program for this input is

Case #1
cannot buy

this is a matching problem but no need to use maximum flow

Posted: Fri Sep 05, 2003 5:39 am
by LittleJohn
coolbila wrote:No, one envelope can appear just one time
my AC program for this input is
Case #1
cannot buy
this is a matching problem but no need to use maximum flow
Yes, I found that for problem says N >= M.
But I have a question, that we can determine if an answer exists or not by maximum flow.
Besides that, how can we derive the best answer without brute-force search?
Or it's an NP problem?
p.s. thanks for gvcormac :wink:

Posted: Fri Sep 05, 2003 5:43 am
by gvcormac
LittleJohn wrote:
coolbila wrote:No, one envelope can appear just one time
my AC program for this input is
Case #1
cannot buy
this is a matching problem but no need to use maximum flow
Yes, I found that for problem says N >= M.
But I have a question, that we can determine if an answer exists or not by maximum flow.
Besides that, how can we derive the best answer without brute-force search?
Or it's an NP problem?
p.s. thanks for gvcormac :wink:
You can use max flow or bipartite match but you don't need to. Since N <= 5 and M <= 10
you can try all possibilities.

Posted: Tue Dec 09, 2003 1:12 am
by Caesum
two points:

firstly only one card can go in one envelope, which the above program is not doing.

secondly i finally passed this through formulating an inequality in the lengths and widths of the card and the envelope and evaluated it with multi-precision arithmetic. maybe its not necessary but i couldnt get ac normally.

Posted: Tue Dec 09, 2003 9:47 am
by Whinii F.
Wow! :) I got AC! Thanks!
It seems you don't need any extensive precision calculation, I just used long double with bsearch.

Posted: Sat Jul 24, 2004 5:20 am
by jackie
At first glance, m = 5 n = 10,

i use brute force to get the answer but the judge said TLE. So i change the algorithm to backTrace and it got AC in 0.002 sec. :)

it's a little difficult to decide whether a rectangle can put in anther one. be patient to caculate every cases .

BTW i use double for the precison