10117 - Nice Milk

All about problems in Volume 101. 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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra »

Does anyone have any test cases....

Should I use real or double .....

Because I always have WA :sad:

Please help...

New poster
Posts: 1
Joined: Wed Mar 27, 2002 2:00 am

Post by srbga »

I am the problem setter
you may send me your code
so that i can check it for u

Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume

Not so nice milk

Post by Yarin »

I've done _many_ submissions on this one now, always WA. I do a BFS on the polygon (together with which edges have been dipped already), "shrinking" one edge being a move. I am certain the polygon clipping routine works, it's been tested a lot. So are there any other things I'm missing? Some strange test case etc.

Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran


Post by Moha »

I have a problem with this.
i use a backtrack approach but i got WA in 1.5 s can anybody send some I/O?
this is my code:

Code: Select all

I got Accepted ;)

New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

10117 - Nice Milk

Post by adelar »

Hi people,
was with error the name of post previous and it was blocked :roll:
I'm trying to solve the problem 10117... something know how I can do paralel lines with a segment with a constant value of distance (h)?

thanks in advance

New poster
Posts: 1
Joined: Sat Oct 06, 2012 5:17 pm


Post by darkloz »

After several WA I don't know what is wrong in my algorithm I just do all possible cuts (the cutting algorithm has been tested in other problems) and compute the minimum remaining area, then the answer is the original area minus the minimum remaining area, is the algorithm wrong? does somebody have special test cases for this problem ?

Thanks in advance.

New poster
Posts: 9
Joined: Wed Jan 13, 2016 3:24 am

Re: 10117 - Nice Milk

Post by pointless0 »

This worked for me: assume the judge input contains concave polygons.

Concave polygon input:

Code: Select all

4 3 2
0 0
5 1
10 0
5 10

0 0 0
AC-ish output:

Code: Select all

Whether or not the judge input actually contains concave polygons I do not know.

Post Reply

Return to “Volume 101 (10100-10199)”