#1145641 (C++23) No.3438 [Cherry 8th Tune D] 競プロは向いてない

• 問題: No.3438 [Cherry 8th Tune D] 競プロは向いてない
• ユーザー: Taiki0715
• 提出日時: 2026-01-23 22:25:21
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 9,094 bytes
• コンパイル時間: 8,374 ms
• コンパイル使用メモリ: 361,104 KB
• 実行使用メモリ: 9,552 KB
• 最終ジャッジ日時: 2026-01-23 22:26:13
• 合計ジャッジ時間: 10,659 ms
• ジャッジサーバーID （参考情報）: judge6 / judge5

ファイルパターン	結果
sample	WA * 1
other	AC * 1 WA * 32

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using P=pair<ll,ll>;
template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;
template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}
template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}
template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<typename T1,typename T2,typename T3>istream &operator>>(istream &is,tuple<T1,T2,T3>&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;}
template<typename T,size_t n>istream &operator>>(istream &is,array<T,n>&a){for(auto&i:a)is>>i;return is;}
template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}
template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}
template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}
template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}
template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}
#define overload3(_1,_2,_3,name,...) name
#define rep1(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__)
#define reps(i,l,r) rep2(i,l,r)
#define all(x) x.begin(),x.end()
#define pcnt(x) __builtin_popcountll(x)
#define fin(x) return cout<<(x)<<'\n',static_cast<void>(0)
#define yn(x) cout<<((x)?"Yes\n":"No\n")
#define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end())
template<typename T>
inline int fkey(vector<T>&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();}
ll myceil(ll a,ll b){return (a+b-1)/b;}
template<typename T,size_t n,size_t id=0>
auto vec(const int (&d)[n],const T &init=T()){
  if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));
  else return init;
}
#ifdef LOCAL
#include<debug.h>
#define SWITCH(a,b) (a)
#else
#define debug(...) static_cast<void>(0)
#define debugg(...) static_cast<void>(0)
#define SWITCH(a,b) (b)
template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}
#endif
struct Timer{
  clock_t start;
  Timer(){
    start=clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(16);
  }
  inline double now(){return (double)(clock()-start)/1000;}
  #ifdef LOCAL
  ~Timer(){
    cerr<<"time:";
    cerr<<now();
    cerr<<"ms\n";
  }
  #endif
}timer;
void SOLVE();
int main(){
  int testcase=1;
  cin>>testcase;
  for(int i=0;i<testcase;i++){
    SOLVE();
  }
}
#include<type_traits>
#include<optional>
template<typename T>constexpr std::enable_if_t<std::is_floating_point_v<T>,T> epsilon(){return 1e-10;}
template<typename T>constexpr std::enable_if_t<std::is_integral_v<T>,T>epsilon(){return 0;}
template<typename T>
struct Point{
  static_assert(std::is_arithmetic_v<T>);
  static constexpr T eps=epsilon<T>();
  T x,y;
  constexpr Point():x(0),y(0){}
  constexpr Point(T x_,T y_):x(x_),y(y_){}
  Point &operator+=(const Point&rhs){
    this->x+=rhs.x;
    this->y+=rhs.y;
    return *this;
  }
  Point &operator-=(const Point&rhs){
    this->x-=rhs.x;
    this->y-=rhs.y;
    return *this;
  }
  Point &operator*=(const T&rhs){
    this->x*=rhs;
    this->y*=rhs;
    return *this;
  }
  Point &operator/=(const T&rhs){
    this->x/=rhs;
    this->y/=rhs;
    return *this;
  }
  friend Point operator+(const Point&lhs,const Point&rhs){return Point(lhs)+=rhs;}
  friend Point operator-(const Point&lhs,const Point&rhs){return Point(lhs)-=rhs;}
  friend Point operator*(const Point&lhs,const T&rhs){return Point(lhs)*=rhs;}
  friend Point operator/(const Point&lhs,const T&rhs){return Point(lhs)/=rhs;}
  friend bool operator==(const Point&lhs,const Point&rhs){return std::abs(lhs.x-rhs.x)<=eps&&std::abs(lhs.y-rhs.y)<=eps;}
  friend bool operator!=(const Point&lhs,const Point&rhs){return !(lhs==rhs);}
  friend std::istream &operator>>(std::istream&is,Point&p){
    is>>p.x>>p.y;
    return is;
  }
  friend std::ostream &operator<<(std::ostream&os,const Point&p){
    os<<p.x<<' '<<p.y;
    return os;
  }
  T arg()const{
    static_assert(std::is_floating_point_v<T>);
    return atan2l(y,x);
  }
  Point<T>rot(T theta)const{
    static_assert(std::is_floating_point_v<T>);
    T s=sin(theta),c=cos(theta);
    return Point(c*x-s*y,s*x+c*y);
  }
  Point<T>rot90(){
    return Point(-y,x);
  }
  T norm()const{return x*x+y*y;}
  template<typename T2=double>
  Point<T2>convert()const{
    Point<T2>res(this->x,this->y);
    return res;
  }
};
template<typename T>
T cross(const Point<T>&a,const Point<T>&b){return a.x*b.y-a.y*b.x;}
template<typename T>
T dot(const Point<T>&a,const Point<T>&b){return a.x*b.x+a.y*b.y;}
//交差する点のうち1つ
template<typename T>
std::conditional_t<std::is_floating_point_v<T>,std::optional<Point<T>>,bool>intersect(const Point<T>&a,const Point<T>&b,const Point<T>&c,const Point<T>&d){
  T ac=cross(d-c,a-c),bc=cross(d-c,b-c),cc=cross(b-a,c-a),dc=cross(b-a,d-a);
  T ab=(b-a).norm(),cd=(d-c).norm();
  if(std::abs(ac)<=epsilon<T>()){
    if((c-a).norm()<=cd+epsilon<T>()&&(d-a).norm()<=cd+epsilon<T>()){
      if constexpr(std::is_floating_point_v<T>)return std::make_optional(a);
      else return true;
    }
    else if(std::abs(bc)<=epsilon<T>()){
      if((c-b).norm()<=cd+epsilon<T>()&&(d-b).norm()<=cd+epsilon<T>()){
        if constexpr(std::is_floating_point_v<T>)return std::make_optional(b);
        else return true;
      }
    }
    if(dot(a-c,b-c)<epsilon<T>()){
      if constexpr(std::is_floating_point_v<T>)return std::make_optional(c);
      else return true;
    }
    if constexpr(std::is_floating_point_v<T>)return std::nullopt;
    else return false;
  }
  if(std::abs(bc)<=epsilon<T>()){
    if((c-b).norm()<=cd+epsilon<T>()&&(d-b).norm()<=cd+epsilon<T>()){
      if constexpr(std::is_floating_point_v<T>)return std::make_optional(b);
      else return true;
    }
    if constexpr(std::is_floating_point_v<T>)return std::nullopt;
    else return false;
  }
  if(std::abs(cc)<=epsilon<T>()){
    if((a-c).norm()<=ab+epsilon<T>()&&(b-c).norm()<=ab+epsilon<T>()){
      if constexpr(std::is_floating_point_v<T>)return std::make_optional(c);
      else return true;
    }
    if constexpr(std::is_floating_point_v<T>)return std::nullopt;
    else return false;
  }
  if(std::abs(dc)<=epsilon<T>()){
    if((a-d).norm()<=ab+epsilon<T>()&&(b-d).norm()<=ab+epsilon<T>()){
      if constexpr(std::is_floating_point_v<T>)return std::make_optional(d);
      else return true;
    }
    if constexpr(std::is_floating_point_v<T>)return std::nullopt;
    else return false;
  }
  if((ac>0)!=(bc>0)&&(cc>0)!=(dc>0)){
    if constexpr(std::is_floating_point_v<T>)return c+(d-c)*cross(b-a,b-c)/cross(b-a,d-c);
    else return true;
  }
  else{
    if constexpr(std::is_floating_point_v<T>)return std::nullopt;
    else return false;
  }
}
template<typename T,bool LOWERHULL=true>
struct ConvexHullTrickDeque{
  static constexpr T inf=std::numeric_limits<T>::max();
  static constexpr T eps=epsilon<T>();
  static inline bool is_concave(const Point<T>&l,const Point<T>&m,const Point<T>&r){
    if constexpr(LOWERHULL)return cross<T>(m-l,r-l)>eps;
    else return cross<T>(m-l,r-l)<eps;
  }
  std::deque<Point<T>>que;
  static constexpr Point<T>none{inf,inf};
  ConvexHullTrickDeque():que(){}
  Point<T>add_left(const Point<T>&v){
    if(que.empty()){
      que.push_front(v);
      return none;
    }
    while(que.size()>=2){
      const Point<T>&m=que[0];
      const Point<T>&r=que[1];
      if(is_concave(v,m,r))break;
      que.pop_front();
    }
    Point<T>res=que.front();
    que.push_front(v);
    return res;
  }
  Point<T>add_right(const Point<T>&v){
    if(que.empty()){
      que.push_back(v);
      return none;
    }
    while(que.size()>=2){
      const Point<T>&l=que[que.size()-2];
      const Point<T>&m=que.back();
      if(is_concave(l,m,v))break;
      que.pop_back();
    }
    Point<T>res=que.back();
    que.push_back(v);
    return res;
  }
};
template<typename T>
std::vector<Point<T>>static_convex_hull(std::vector<Point<T>>points){
  std::sort(points.begin(),points.end(),[](const Point<T>&lhs,const Point<T>&rhs){return lhs.x==rhs.x?lhs.y<rhs.y:lhs.x<rhs.x;});
  points.erase(std::unique(points.begin(),points.end()),points.end());
  if(points.size()<=2)return points;
  ConvexHullTrickDeque<T,true>lower;
  ConvexHullTrickDeque<T,false>upper;
  for(const Point<T>&p:points)lower.add_right(p),upper.add_right(p);
  std::vector<Point<T>>res(lower.que.begin(),lower.que.end());
  res.insert(res.end(),upper.que.rbegin()+1,upper.que.rend()-1);
  return res;
}
bool comp(Point<ll>a,Point<ll>b){
  if(a.x!=b.x)return a.x<b.x;
  return a.y<b.y;
}
void SOLVE(){
  int n;
  cin>>n;
  vector<Point<ll>>a(n);
  cin>>a;
  auto hull=static_convex_hull(a);
  sort(all(hull),comp);
  rep(i,n){
    if(binary_search(all(hull),a[i],comp)){
      cout<<a[i]<<'\n';
    }
    else cout<<"No\n";
  }
}