•  

    算法导论的课后习题、要求给出点集的极角排序的叉乘实现,(极坐标系)。
    复杂度要求O(n*lg n),就用堆的数据结构来做。初学计算几何,没见过真正的极角排序,自己YY一个模板。
    大致如下,要求顺逆时针输出都可以,只要稍作调整。要求输出起点的话,可以用二分查找到起点,让后按时针序输出其他点,也只要稍作调整。
    01
    02
    03
    04
    05
    06
    07
    08
    09
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71

     

    #include 
    #include 
    #include 
    #include 
    using namespace std; 
    #define maxn 100 
    //用堆排序来实现极角排序,关键在于用叉乘比较极角大小 
    struct point{ 
        int x; 
        int y; 
    }; 
    typedef struct point point; 
    int n,heapSize; 
    point heap[maxn],O;//极角坐标系原点 
     
    int cross(point p1,point p2){ //p1 叉乘 p2: 小于零表示p1在p2的逆时针方向。 
        return  
        (p1.x-O.x)*(p2.y-O.y)-(p2.x-O.x)*(p1.y-O.y); 

     
    void heapfy(int idx){//保持堆的性质 
        int l = idx << 1
        int r = idx << 1 |1
        int est; 
     
        if(l > heapSize )return
     
        if(cross(heap[idx],heap[l]) < 0)//左孩子的极角是否比父节点大 
            est = idx; 
        else  est = l; 
     
        if(r <= heapSize && cross(heap[r],heap[est]) < 0
            est = r;                                //找到极角最大矢量的下标 
        if(est != idx ){ 
            swap( heap[est] , heap[idx] ); 
            heapfy(est);                        
        } 
         

     
    void build(){ 
        for(int i= heapSize/2; i > 0; i--)   //heap从下标1开始存到 heapSize  / 2 都是内部节点  
            heapfy(i); 

     
    void heapSort(){ 
        heapSize=n; 
        build();     
        for(int i=1;i < n; i++){ 
            swap( heap[1] , heap[heapSize--] ); 
            heapfy(1); 
        } 

     
    int main(){ 
        while(scanf("%d", &n) != EOF){ 
            O.x=0
            O.y=0
            for(int i = 1; i <= n; i++) 
                scanf("%d%d", &heap[i].x, &heap[i].y); 
     
            heapSort(); 
     
            for(i=1; i <= n; i++) 
                printf("(%d,%d)\n",heap[i].x,heap[i].y); 
        } 
        return 0

     


     

  • 01
    02
    03
    04
    05
    06
    07
    08
    09
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    // 判给定线段和是否相交 
     
    #include 
    #define  max(a,b) a > b ? a : b 
    #define  min(a,b) a < b ? a : b 
     
    typedef struct { 
         double x, y; 
    } point; 
    double direction (point p1, point p2, point p3) 

         return (p3.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p3.y - p1.y); 

     
    bool OnSegment (point p1, point p2, point p3) 

         double minx, miny, maxx, maxy; 
         minx = min(p1.x, p2.x); 
         maxx = max(p1.x, p2.x); 
         miny = min(p1.y, p2.y); 
         maxy = max(p1.y, p2.y); 
         //考虑水平和垂直的特殊情况,x,y的范围都要判断 
         if(p3.x >= minx && p3.x <= maxx && p3.y >= miny && p3.y <= maxy) 
              return true
         else 
              return false

     
    bool segments_intersect(point p1, point p2, point p3, point p4) 

         double d1, d2, d3, d4; 
         d1 = direction(p3, p4, p1); 
         d2 = direction(p3, p4, p2); 
         d3 = direction(p1, p2, p3); 
         d4 = direction(p1, p2, p4); 
         if (d1 * d2 < 0 && d3 * d4 < 0
              return true
         else if (d1 == 0 && OnSegment (p3, p4, p1)) 
              return true
         else if (d2 == 0 && OnSegment (p3, p4, p2)) 
              return true
         else if (d3 == 0 && OnSegment (p1, p2, p3)) 
              return true
         else if (d4 == 0 && OnSegment (p1, p2, p4)) 
              return true
         return false