11066 - Aragorn

[CodeMaker]

Hi, as far as i understand this problem is about concave polygon intersection ( or may be i should say, polygon clipping) or atleast i am trying to do so.

i managed to code it up according to some algorithm available. bad luck! i got wrong answer. the algorithm i am using gives approximate answer when there are vertices on the edge of other polygon. but it shouldn't be effecting much in case of area calculation.

all the simple hand made data passed out. and it is difficult to check big cases by hand. so i need some help. i am not sure is it all about precision error or anything else.

someone please help me to check my code.

is the following I/O correct?

Input:

Code: Select all

2
0 0
100 0
2
0 0
100 0

2
0 10 
100 10
2
0 15
100 15

3
0 100
50 50
100 100
2
0 50
100 50

3
0 100
50 50
100 100
2
0 51
100 51

3
0 0
10000 10000
20000 0
2
0 10000
20000 10000


5
1 7
3 11
4 5
5 11
7 7

5
0 1
2 11
4 7
6 11
8 1

2
0 0 
10000 0
3
0 0
5000 5000
10000 0


7
0 6
3 4
1 1
4 3
7 1
5 4
8 6
5
0 4
3 3
4 0
5 3
8 4

0

Output:

Code: Select all

0.00
333.33
0.00
1.00
33333200.00
3.33
24999975.00
2.91

Can i get some more data?
thanks a lot...

[david]

My program outputs

0.00
500.00
0.00
1.00
100000000.00
3.33
25000000.00
4.73

Anyway, it would have been easy for you to check most of your answers by hand.

[CodeMaker]

thanks a lot for your quick reply.

yes, i should have calculated atleast the 2nd input by hand. i added some of them before posting. but i will check whats wrong.
thanks again.

[CodeMaker]

Hi, just got Accpeted in this problem.

by the way. is there a way to solve this problem without clipping?
my code took 0.3 sec but thats not what i m sorry about rather i am sorry because it is huge ( 1000+ lines ). i have difficulty of understanding the available algorithms, because they were poorly written ( in the materials i have). i will try to short things up by replacing my C code by C++

by the way, those who got AC , do you care to tell me the size of your code?

is there anything that you can reffer and that i can use to improve my code?

my previous code was of 200 lines but it cant handle degenerated polygons.

thanks a lot ....

[david]

I don't know what you mean by "clipping". I simply build the curve that is the "minimum" of the two given (you just need to find their points of intersection, which can be done in linear time) and substract areas. My code, excluding the pre-written geometric routines for segment intersection, is 60 lines long.

[mf]

by the way, those who got AC , do you care to tell me the size of your code?

69 lines, 1441 bytes.

My algorithm consists in just integrating function max(0, M(x)-C(x)) over a given interal, where M(x) is height of mountains at coordinate x, and C(x) is height of clouds at x. I represent M(x)-C(x) as a set of linear segments, do clipping, and then simply sum remaining areas.

[CodeMaker]

hi, thanks to all of you for pointing to my mistake.

i just did it in the hard way. made 2 polygons with the 2 curves. by increasing infinitly in the opposite sides. and then took the intersection of the 2 polygons. as you can understand how complicated this algorithm can be.

though my code will work for randomly generated curves, even with self intersection ( even it can print all the cut polygons in correct order and can do any set operations), there is no point of doing something in the stupid way. i hope sometime in future this code might become useful. that is all that i can wish.

thanks again for your reply.

[sluga]

The last input is not legal because it is unsorted, so the output is also wrong. When you sort it, the correct output is 5.40

In the third input from the end, the clouds start at (1, 7), but they should always start at (0, y) and mountains are longer than clouds, so this is also an illegal input.