Back Junアルゴリズム11650号:座標を整列

質問リンク

https://www.acmicpc.net/problem/11650

制限

質問する

2 D平面上のN個の点を与える.x座標のインクリメント順に座標を並べ、x座標が同じ場合はy座標のインクリメント順に座標を並べ、プログラム出力を記述します.

入力

第1行は、点の個数N(1≦N≦100000)を与える.2行目から、N行においてi番点の位置xiとyiが与えられる.(−1000≦xi,yi≦100000)座標は常に整数であり、2つの位置が同じ点はない.

しゅつりょく

最初の行からN行の位置合わせの結果を出力します.

入力と出力の例

に答える

x,yの並べ替えを容易にするために構造体を用いた.

テストケース変数を宣言し、動的割当てを使用して対応するメモリ割当てを取得し、xとyの値を入力します.

qsortを利用するために、比較関数を定義します.

問題ではxの値をインクリメンタルで並べ替え、xの値が同じ場合はyの値をインクリメンタル方向に並べ替え、compare関数でvoid値a,bを受け入れ、Point形式で逆参照して構造体AとBを宣言する.

条件文を用いてA.x>B.xを1(昇順)並べ替え、
A.x=B.xであればyの値を増やし、そうでなければ-1を返します.

整列の結果を出力します.

プールコード

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int x;
  int y;
} Point;

int compare(const void *a, const void *b){
  Point A = *(Point *)a;
  Point B = *(Point *)b;
  if(A.x > B.x){
    return 1;
  }
  else if(A.x == B.x){
    if(A.y > B.y){
      return 1;
    }
    else{
      return -1;
    }
  }
  return -1;
}

int main(){
  int test;
  scanf("%d",&test);
  Point *arr;
  arr = (Point *)malloc(sizeof(Point) * test);
  for(int i = 0; i < test; i++){
    scanf("%d %d",&arr[i].x,&arr[i].y);
  }
  qsort(arr,test,sizeof(Point),compare);
  for(int i = 0; i < test; i++){
    printf("%d %d\n",arr[i].x,arr[i].y); 
  }
  free(arr);
  return 0;
}

ふくガス

これは速いソートを練習するのに良い問題だと思います.
実現するには何の困難もない.