parina's blog

Sorting points counter-clockwise from given points on Geometry
By parina, 13 years ago, In English

[code]
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;
#define i64 long long
#define sq(a) ((a)*(a))

struct point{
    i64 x,y;
 }p[1000000],p0;


////distance between two points
 i64 dist(const point &a, const point &b) {
    return sq(a.x-b.x) + sq(a.y-b.y);
}



////Area of three points to find left turn or right
i64 xmult(point a,point b,point c)
{
return a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
}



bool cmpp(const point &a,const point &b)
{

/*if area >0 then angleof b > angleof a
area=0 means co-linear
*/
if(xmult(p0,a,b) > 0)
           return true;
else if (xmult(p0,a,b)==0&& dist(p0,a)<dist(p0,b) )
           return true;

return false;
}





bool cmp2(const point &a,const point &b)
{
if(xmult(p0,a,b) > 0)
           return true;
else if (xmult(p0,a,b)==0&& dist(p0,a)<dist(p0,b) )
           return true;

return false;
}




int main(){
long n,i,j,k,t,l,top,ke1,ke;
i64 cx,cy;
char c,d;

point op;

scanf("%ld",&t);
for(l=0;l<t;l++){
scanf("%ld",&n);
j=0;
for(i=0;i<n;i++){
scanf("%lld %lld%c%c",&cx,&cy,&d,&c);
if(c=='Y'){
    p[j].x=cx;    p[j].y=cy;    j++;
    }
}

ke1=0;
op=p[0];
for(i=1;i<j;i++){
if(p[i].x<op.x ||(p[i].x==op.x&&p[i].y<op.y)){
   op=p[i];
    ke1=i;
    }
}

//reference point ,swapping with p[0]
swap(p[0],p[ke1]);


p0=p[0];
sort(p+1,p+j,cmp2);







ke1=0;
op=p[0];

for(i=1;i<j;i++){
if(p[i].x>op.x||(p[i].x==op.x&&p[i].y>op.y)){
   op=p[i];
    ke1=i;
    }
}

p0=p[ke1];
sort(p+ke1,p+j,cmpp);


printf("%ld\n",j);
for(i=0;i<j;i++){
printf("%lld %lld\n",p[i].x,p[i].y);
}
}
return 0;
}
[/code]

I wanna learn more....
[email protected]
  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think this comparer is not transitive (it's kind of cyclic), and it's incorrect to sort using it (maybe STL should have assertions about it in debug mode in visual studio)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I didn't get you. In this code I have taken points arbitarily and sorted them counterclockwise in point p[] starting from leftmost point. And this is correct. 
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I agree with al13n. This comparator seems not to be transitive.

      If cross product of A and B > 0 and cross product of B and C > 0, it does not necessarily mean that cross product of A and C > 0, that said for your comparator A>B && B>C doesn't guarantee that A > C, which is required for std::sort

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        CAn you tell me in which line you are disagreed? I am new to programming and didn't get you..So please 
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Consider three vectors: a=(0,1), b=(-1,-1), and c=(1,-1). Your comparer will say either a<b<c<a or a>b>c>a (I'm not sure which one). So it's impossible to sort these vectors using this comparer because there's a cycle in comparisons. All permutation of these vectors will be neither increasing nor decreasing. However, this method is valid if all vectors are in one semi-plane, in this case such cycles are impossible.
          → Reply