test/yosupo/sort_points_by_argument.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 16:41:24+09:00
• Problem: https://judge.yosupo.jp/problem/sort_points_by_argument

Depends on

• geometry/argsort.cpp

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/sort_points_by_argument

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../geometry/argsort.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n;
  cin>>n;

  using ll = long long;
  struct Point{ll x,y;};
  vector<Point> ps(n);
  for(int i=0;i<n;i++) cin>>ps[i].x>>ps[i].y;

  argsort(ps);

  for(int i=0;i<n;i++) cout<<ps[i].x<<" "<<ps[i].y<<"\n";
  cout<<flush;
  return 0;
}

#line 1 "test/yosupo/sort_points_by_argument.test.cpp"
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/sort_points_by_argument

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "geometry/argsort.cpp"

#line 3 "geometry/argsort.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// (-pi, pi], atan2(0, 0) = 0
template<typename P>
void argsort(vector<P> &ps){
  auto getA=
    [&](P p){
      if(p.x>=0 and p.y>=0) return 0;
      if(p.y>=0) return 1;
      if(p.x<=0) return -2;
      return -1;
    };
  auto cross=[&](P a,P b){return a.x*b.y-a.y*b.x;};
  auto cmp=
    [&](P a,P b){
      if(getA(a)!=getA(b)) return getA(a)<getA(b);
      if(a.x==0 and a.y==0) return !(b.x==0 and b.y==0);
      if(b.x==0 and b.y==0) return false;
      return cross(a,b)>0;
    };
  sort(ps.begin(),ps.end(),cmp);
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 8 "test/yosupo/sort_points_by_argument.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n;
  cin>>n;

  using ll = long long;
  struct Point{ll x,y;};
  vector<Point> ps(n);
  for(int i=0;i<n;i++) cin>>ps[i].x>>ps[i].y;

  argsort(ps);

  for(int i=0;i<n;i++) cout<<ps[i].x<<" "<<ps[i].y<<"\n";
  cout<<flush;
  return 0;
}

Back to top page