|
|
вернуться в форум2 coord? Is it posible to solve it using only the first 2 coordinates? I already found a solution but it uses 3 coordinates and I have to read all coordinates first. Hmm. My solution uses all vertices. Could you explain solution with 3 coords. Mine inside. For each line segment (x1; y1) (x2; y2) I calculate cross product of 2 vectors: (0; 0) (x1; y1) and (0; 0) (x2; y2) Summing all cross products gives double square of polygon but with one exception: it is positive if vertices are situated ccw and negative otherwise (cw). Re: Hmm. My solution uses all vertices. Could you explain solution with 3 coords. Mine inside. Just look for the upper, the lower and the most to the right points. Then label then acording on how you found them (e.g.: if you find the lower first then you give it a lower number than the upper point, I used "i" for this). Then you just have to check the sequence. If you have any problem understanding this, I can post my solution. PS: This algorithm has a small bug that you don't have to fix in order to get AC! What's the bug to this algorithm? Послано ValBG 7 май 2003 00:46 Vallery777@yahoo.com What about the sample input? Послано ValBG 7 май 2003 01:36 My program uses the following method: I choose the upper, lower and rightmost points and then sort them in the order they were visited. Suppose their coordinates are (x1,y1), (x2,y2), (x3,y3), where 1 was the first visited, 2 - second and 3 - third. Then I put them in a martix x1 y1 1 x2 y2 1 x3 y3 1 and calculate D=x1*y2*1-x3*y2*1. If D>0, the 3 points are oriented clockwise. When D<0, then orientation is counterclockwise. But what happens when D=0? And why is my method wrong for the sample input? Pls help me! Vallery777@yahoo.com |
|
|