11106 - Rectilinear Polygon

[rammestain]

how this problem can be solved?

[sclo]

sorting

[Jan]

I think this is a beautiful problem. I liked it very much. A point is part of exactly one vertical and one horizontal edge. Suppose the first point is (x,y). Try to find out two points (x,w) and (z,y). And continue searching until no point is left. To find these two points you have to maintain a strategy.

I m giving a test case. Draw it on a paper and try to find a strategy to build the polygon.

Input:

Code: Select all

1
30
2 0
2 4
16 0
8 1
9 1
11 1
10 1
10 4
9 7
5 4
6 7
5 7
5 8
12 10
8 7
6 8
5 12
9 10
10 10
12 12
13 10
13 9
13 7
13 4
16 4
10 9
10 7
11 4
10 2
9 2

Output:

Code: Select all

82

Hope it helps.

[vinay]

there r duplicate points in the input too..

how to handle them ....

i printed -1 for that but gat WA...

i then erased them form the list then too wa...

don't know what to do

[vinay]

btw is my observation right that if no. of "distinct" points is odd then no rectilinear polygon is possible ...
if not whats the counter example...

[Jan]

The problem states...

each vertex is an endpoint of exactly one horizontal edge and one vertical edge

And the edges are vertical or horizontal. So, we need even number of points.

[vinay]

yeah thats what I meant...

wat about my second n more imporatant question??

there are duplicate points in the input ...

hoe to handle those???

[little joey]

There must be something wrong with your program, because there are _no_ duplicate points in the input.

[vinay]

my algo is something like this:

1) get two sorted lists , one by X and other by Y coordinates...
2) in each list check whether we can forms pairs ... by pair i mean same
coordinate value by which the list is sorted.. if not -1

3) else we have an answer which is the sum of the other co-ordinates of the pairs ...

am i right???

[vinay]

here is my code...
I assure i will remove it as soon as i get the flaw in it..

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include <functional>      // For greater<int>( )
#include<cassert>

using namespace std;
struct node{
        int x;
        int y;
        //int num;
};    
 
bool UDgreater(node a,node b){
    if(a.x==b.x) 
            return a.y<b.y;
        
    return a.x<b.x;
} 

bool UDgreater1(node a,node b){
    if(a.y==b.y)
        return a.x<b.x;
         
    return a.y<b.y;
}   


int main(){
   
    int cases,nn;
    scanf("%d",&cases);
    
    while(cases--){

            scanf("%d",&nn);
            vector<node> v;
            node n;
            
            //input points
            for(int i=0;i<nn;i++){
                
                scanf("%d%d",&n.x,&n.y);
                v.push_back(n);
            }    
          
            // horizonal and vertical lists...
            vector<node > H=v;
            
            sort(v.begin(),v.end(),UDgreater);
            sort(H.begin(),H.end(),UDgreater1);
            
            f=false;
            int ret=0;
            for(int i=0;i<nn-1;i+=2){
                
                //pair not found..
                if(v[i].x!=v[i+1].x){
                    printf("-1\n");
                    f=true;
                    break;
                }
                // pair found add y coordinate
                ret+=abs(v[i+1].y-v[i].y);
                
                // pair not found..
                if(H[i].y!=H[i+1].y){
                    printf("-1\n");
                    f=true;
                    break;
                }       
                // pair found add x coordinate
                ret+=abs(H[i+1].x-H[i].x); 
            }    
            if(f) continue;
                        
            printf("%i\n",ret);
            
     }
     return 0;
}            

[navid_a2b]

can any one tell me what is wrong with my code ? thanks in advance

Code: Select all

removed

[vinay]

the idea is same with your code too...

so whats wrong with me , is wrong with u....

btw i checked for duplicate points using assert function n it gave runtime error.. doesn't it mean that there r duplicate points?

[little joey]

the idea is same with your code too...

so whats wrong with me , is wrong with u....

btw i checked for duplicate points using assert function n it gave runtime error.. doesn't it mean that there r duplicate points?

Well, I also checked with assert, and my code runs fine.

About your code: it will not compile, because the variable f is not declared.
Try this input:

Code: Select all

1
8
0 0
0 2
2 0
2 2
1 1
1 3
3 1
3 3

The answer should not be 16.

[vinay]

that means my algo is wrong....



so do i need to simulate the process of choosing a horizontal path and then a vwrticale path alternately....

or there is other way possible , ie without simulation...

[little joey]

No, your method is correct, but you just need one additional step.