vishva1994's blog

Codechef June long 2015 _ CHPLGNS
By vishva1994, history, 9 years ago, In English

Question : http://www.codechef.com/problems/CHPLGNS
My Solution : http://www.codechef.com/viewsolution/7305267

Where am i going wrong ? Why WA . I am finding area and then counting . Help required .

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

area concept is not right....suppose u have a bigger square and a smaller square outside the bigger square.... then ur solution gives that smaller square is inside the bigger square....which is wrong....

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    His concept is right! Just read the question again!

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can i get any ideas where i am going wrong . Thank you

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Just cross check your formula for finding the area of the polygon

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think, you don't even need to calculate the area of the polygon

My Idea, for every polygon find out the max(x's), min(x's), max(y's), min(y's) . This will look like rectangle. Thus sorting on any one axis(x's or y's) you can find the result. or you can calculate the area of rectangle and sort and get the result.

I can see that there is an editorial to this problem. Why not read that ? BTW, the second idea of editorial is similar to mine

→ Reply