10053 - Envelopes

[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

[gvcormac]

[incorrect comment deleted]

[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

[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..

[Caesum]

it will fit in diagonally

[Whinii F.]

That was the way..

I was so silly

[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,

[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

[LittleJohn]

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

[gvcormac]

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.

[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.

[Whinii F.]

Wow! I got AC! Thanks!
It seems you don't need any extensive precision calculation, I just used long double with bsearch.

[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