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

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

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

ソースコード

#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;
}
//a,b,cがこの順に同一直線上にあるか
template<typename T>
bool on_segment(Point<T>a,Point<T>b,Point<T>c){
  b-=a,c-=a;
  if(std::abs(cross(b,c))>epsilon<T>())return false;
  T d=dot(b,c);
  return -epsilon<T>()<=d&&d<=dot(c,c)+epsilon<T>();
}
/*
pointsは反時計回り
1:内側
0:境界上
-1:外側
*/
template<typename T>
int convex_polygon_inout(const std::vector<Point<T>>&points,Point<T>p){
  int n=points.size();
  if(n==1)return points[0]==p?0:-1;
  if(n==2)return on_segment(points[0],p,points[1])?0:-1;
  if(cross(points[1]-points[0],p-points[0])<-epsilon<T>())return -1;
  if(on_segment(points[0],p,points[n-1]))return 0;
  if(on_segment(points[0],p,points[1]))return 0;
  if(cross(points[n-1]-points[0],p-points[0])>=-epsilon<T>())return -1;
  int l=1,r=n-1;
  while(r-l>1){
    int mid=(l+r)/2;
    if(cross(points[mid]-points[0],p-points[0])>=-epsilon<T>())l=mid;
    else r=mid;
  }
  T c=cross(points[l+1]-points[l],p-points[l]);
  if(c>epsilon<T>())return 1;
  else if(c<-epsilon<T>())return -1;
  else return 0;
}
bool operator<(Point<ll>a,Point<ll>b){
  if(a.x!=b.x)return a.x<b.x;
  return a.y<b.y;
}
constexpr ll inf=1e18;
void SOLVE(){
  int n;
  cin>>n;
  vector<Point<ll>>a(n);
  cin>>a;
  auto hull=static_convex_hull(a);
  int m=hull.size();
  vector<pair<Point<ll>,Point<ll>>>ans(m);
  Point<ll>g;
  rep(i,m)g+=hull[i];
  g.x/=m,g.y/=m;
  if(convex_polygon_inout(hull,g)==1){
    rep(i,m){
      ans[i]={hull[i],hull[i]-g};
    }
  }
  else{
    rep(i,m){
      Point<ll>pre=i?hull[i-1]:hull[m-1];
      Point<ll>nxt=i+1<m?hull[i+1]:hull[0];
      ans[i]={hull[i],hull[i]*2-pre-nxt};
    }
  }
  sort(all(ans));
  rep(i,n){
    auto itr=lower_bound(all(ans),make_pair(a[i],Point<ll>{-inf,-inf}));
    if(itr!=ans.end()&&itr->first==a[i])cout<<itr->second<<'\n';
    else cout<<"No\n";
  }
}