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

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

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

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