H1 计算几何通用

/*EHnotgod————
..............#######.....#.....#..............
..............#...........#.....#..............
..............#######.....#######..............
..............#...........#.....#..............
..............#######.....#.....#..............
*/

// 1.头文件(EH:?这也能算第一点?)
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define M_PI acos(-1)
#define range(i, a, b) for (int i = (a); i < (b); ++i)
typedef long double T;
// template<class T> string ts(const T& v){
//     stringstream ss; ss << v; return ss.str();
// }
// template<class A,class B> string ts(const pair<A,B>& p){ return "("+ts(p.first)+","+ts(p.second)+")"; }
// template<class T> string ts(const vector<T>& v){ string s="{"; for (auto &x:v) s += ts(x)+","; return s+"}"; }
// template<class T, class C, class A> string ts(const set<T,C,A>& v){ string s="{"; for (auto &x:v) s += ts(x)+","; return s+"}"; }
// template<class T, class C, class A> string ts(const multiset<T,C,A>& v){ string s="{"; for (auto &x:v) s += ts(x)+","; return s+"}"; }
// template<class K,class V,class C, class A> string ts(const map<K,V,C,A>& m){ string s="{"; for (auto &kv:m) s += ts(kv.first)+":"+ts(kv.second)+","; return s+"}"; }
// void dbg_out(){ cerr << "\n"; }
// template<class H, class...T> void dbg_out(const H& h, const T&...t){
//     cerr << " " << ts(h);
//     dbg_out(t...);
// }
// #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",dbg_out(__VA_ARGS__)

// 2.1 点
// 2.1.1基本定义
struct pt{
    T x, y;
    pt operator+(pt p){return{x+p.x, y+p.y};}
    pt operator-(pt p){return{x-p.x, y-p.y};}
    pt operator*(T d){return{x*d, y*d};}
    pt operator/(T d){return{x/d, y/d};} //注意不能除以0
    bool operator<(const pt& a) const {
    if (x != a.x) return x < a.x;
        return y < a.y;
    }
    bool operator==(const pt& other) const { return x == other.x && y == other.y; }
    bool operator!=(const pt& other) const { return !(*this == other); }
};
T sq(pt p) {return p.x*p.x+ p.y*p.y;}
T absv(pt p){return sqrt(sq(p));}
ostream&operator<<(ostream&os, pt p){
    return os <<"("<< p.x<<","<< p.y<<")";
}
int sgn(T x){return(T(0)< x)-(x <T(0));}
// 2.1.3基本变换：平移
pt translate(pt v, pt p){
    return p + v;
}
// 2.1.4基本变换：缩放
pt scale(pt c,T factor, pt p){
    return c +(p - c)* factor;
}
// 2.1.5基本变换：旋转（逆时针）
pt rot(pt p,T a){
    return{p.x*cos(a)- p.y*sin(a), p.x*sin(a)+ p.y*cos(a)};}
pt perp(pt p){
    return{-p.y, p.x};
}
// 2.1.6 点积
T dot(pt v, pt w){
    return v.x* w.x+ v.y* w.y;
}
bool isPerp(pt v, pt w){
    return dot(v, w)==0;
}
// 2.1.7 叉积
T cross(pt v, pt w){return v.x* w.y- v.y* w.x;}
T angle(pt v, pt w){
    return abs(atan2(cross(v, w), dot(v, w)));
}
T orient(pt a, pt b, pt c){return cross(b - a, c - a);}
bool inAngle(pt a, pt b, pt c, pt p){
    assert(orient(a, b, c)!=0);
	if(orient(a, b, c)<0)swap(b, c);
	return orient(a, b, p)>=0&&orient(a, c, p)<=0;
}
T orientedAngle(pt a, pt b, pt c){
    if(orient(a, b, c)>=0){return angle(b - a, c - a);}
	else{return 2* M_PI -angle(b - a, c - a);
}
}
// 2.1.8 极角排序
bool half(pt p){
	return p.y>0||(p.y==0&& p.x<0);
}
void polarSort(vector<pt>&v){
    sort(v.begin(), v.end(),[](pt v, pt w){
        return make_tuple(half(v),0,sq(v))<
            make_tuple(half(w),cross(v,w),sq(w));
    });
}

// 2.2 直线
// 2.2.1 基本定义
struct line{
    pt v; T c;
    line(pt v, T c):v(v),c(c){} // 点斜式
    line(T a, T b, T c):v({b,-a}),c(c){} // 标准式(ax+by+c=0)
    line(pt p, pt q):v(q-p),c(cross(v,p)){} // 两点式
};
// 2.2.2点与直线的位置关系
T side(line ln, pt p){
    return cross(ln.v, p)- ln.c;}
// 2.2.3点到直线的距离
T dist(line ln, pt p){return abs(side(ln, p))/absv(ln.v);}
// 2.2.4过一点的垂线
line perpThrough(line ln, pt p){return{p, p +perp(ln.v)};}  
// 2.2.5沿直线排序   
bool cmpProj(line ln, pt p, pt q){return dot(ln.v, p)<dot(ln.v, q);}   
// 2.2.6沿指定方向平移    
line translate(line ln, pt t){return{ln.v, ln.c +cross(ln.v, t)};} 
// 2.2.7直线交点  
bool inter(line l1, line l2, pt &out){
    T d =cross(l1.v, l2.v); if(d == 0)return false;
    out =(l2.v* l1.c- l1.v* l2.c)/ d;
    return true;
}
// 2.2.8正交投影与反射
pt proj(line ln, pt p){return p -perp(ln.v)*side(ln, p)/sq(ln.v);}
pt refl(line ln, pt p){return p -perp(ln.v)*2*side(ln, p)/sq(ln.v);}
// 2.2.9点到直线的平方距离
T sqDist(line ln, pt p) {
    return side(ln, p) * side(ln, p) / sq(ln.v); 
}
// 2.3 线段
// 2.3.0 定义?没有定义，线段不TM就两个点吗
// 2.3.1点在线段为直径的圆上    
bool inDisk(pt a, pt b, pt p){return dot(a - p, b - p)<=0;}
// 2.3.2点在线段上    
bool onSegment(pt a, pt b, pt p){
    return orient(a, b, p)==0 && inDisk(a, b, p);
}
// 2.3.3线段与线段交点    
bool properInter(pt a, pt b, pt c, pt d, pt &out){    
    T oa =orient(c, d, a), ob =orient(c, d, b),         
      oc =orient(a, b, c), od =orient(a, b, d);
	if(oa * ob <0&& oc * od <0){
    	out =(a * ob - b * oa)/(ob - oa);
    	return true;
    }
	return false;
}
set<pt>inters(pt a, pt b, pt c, pt d){
  pt out;        
  if(properInter(a, b, c, d, out))return{out};  
  set<pt> s;      
  if(onSegment(c, d, a)) s.insert(a);
  if(onSegment(c, d, b)) s.insert(b);
  if(onSegment(a, b, c)) s.insert(c);
  if(onSegment(a, b, d)) s.insert(d);
  return s;
}// 如果|s|=1则只有一个交点；如果|s|=2则说明相交的区域是一条线段，并且中存的是其他两个端点

// 2.3.4点到线段的距离
T segPoint(pt a, pt b, pt p){
    if(a != b){
    	line l(a, b);
    	if(cmpProj(l, a, p)&& cmpProj(l, p, b))
            return dist(l, p);
		return min(absv(p - a),absv(p - b));
    }
	return absv(p - a);
}

// 2.3.5线段到线段的距离  
T segSeg(pt a, pt b, pt c, pt d){
  pt dummy;    
  if(properInter(a, b, c, d, dummy))return 0;
  return min({segPoint(a, b, c),segPoint(a, b, d), 
              segPoint(c, d, a),segPoint(c, d, b)});
}

// 2.4 多边形
// 2.4.1多边形面积
T areaPolygon(vector<pt>p){
    T area =0.0;
	for(int i =0, n = p.size(); i < n; i++){
    	area +=cross(p[i], p[(i +1)% n]);
    }
	return abs(area)/2.0;
}
// 2.4.2 射线法：判断点是否在多边形内部
bool above(pt a, pt p){
    return p.y>= a.y;
}
bool crossesRay(pt a, pt p, pt q){
    return(above(a, q)-above(a, p))*
    	orient(a, p, q)>0;
}
// 这个strict可以自己调控，如果 strict=true（默认值），点在边上返回 false。如果 strict=false，点在边上返回 true。
bool inPolygon(vector<pt>p, pt a, bool strict=true){
    int numCrossings =0;
	for(int i =0, n = p.size(); i < n; i++){
        if(onSegment(p[i], p[(i +1)% n], a))return!strict;
            numCrossings +=crossesRay(a, p[i], p[(i +1)% n]);
    }
    return numCrossings & 1;
}
// 2.4.3凸包
bool turn_left(pt a, pt b, pt c) { 
    return sgn(cross(b - a, c - a)) > 0; 
}
vector<pt> convex_hull(vector<pt> a) {
    if (a.size() <= 2) return a;
    pt base = *min_element(a.begin(), a.end());
    sort(a.begin(), a.end(), [&](auto u, auto v) {
        return make_tuple(half(u - base), 0) < make_tuple(half(u - base), cross(u - base, v - base));
    });
    vector<pt> ret;
    for (auto i : a) {
        while (ret.size() > 1 && !turn_left(ret[ret.size() - 2], ret[ret.size() - 1], i)) 
            ret.pop_back();
        ret.push_back(i);
    }
    return ret;
}

// 2.4.4 CCW判点-严格判断点 p 是否在凸多边形 A（CCW）内部，但是A必须逆时针排列
bool pointInConvexStrict(const vector<pt>& A, const pt& p) {
    int n = (int)A.size();
    if (n < 3) return false;
    if (sgn(orient(A[0], A[1], p)) <= 0) return false;
    if (sgn(orient(A[0], A[n-1], p)) >= 0) return false;

    int l = 1, r = n - 1;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (sgn(orient(A[0], A[mid], p)) > 0) l = mid;
        else r = mid;
    }
    return sgn(orient(A[l], A[l+1], p)) > 0;
}

// 2.5圆
// 2.5.1 外接圆，返回的是外心！别问我为啥不返回半径，要算的话，自己逮个点算不就得了
pt circumCenter(pt a, pt b, pt c){
  b = b - a, c = c - a;
  assert(cross(b, c)!=0);
  return a +perp(b *sq(c)- c *sq(b))/cross(b, c)/2;
}

// 2.5.2圆与直线的交点
int circleLine(pt o,T r, line ln,pair<pt, pt>&out){
    T h2 = r * r - sqDist(ln, o);
	if(h2 >= 0){
    	pt p = proj(ln, o);
    	pt h = ln.v*sqrt(h2)/absv(ln.v);
        out = {p - h, p + h};
    }
	return 1+sgn(h2);
}

// 2.5.3圆与圆的交点
int circleCircle(pt o1,T r1, pt o2,T r2, pair<pt, pt>&out){
    pt d = o2 - o1;    
    T d2 =sq(d);
    if(d2 == 0){
        assert(r1 != r2);
		return 0;
    }
	T pd =(d2 + r1 * r1 - r2 * r2)/2;
    T h2 = r1 * r1 - pd * pd / d2;
    if(h2 >=0){ pt p = o1 + d * pd / d2, h =perp(d)*sqrt(h2 / d2); out = {p - h, p + h};}
    return 1 + sgn(h2);
}
bool inTri(pt a,pt b,pt c,pt p){
 return orient(a,b,p)>=0&&orient(b,c,p)>=0&&orient(c,a,p)>=0;
}
vector<tuple<pt,pt,pt>> earCut(vector<pt>p){
 int n=p.size(),c=n;vector<int>l(n),r(n),v(n,1);deque<int>q;
 vector<tuple<pt,pt,pt>>z;
 range(i,0,n)l[i]=(i+n-1)%n,r[i]=(i+1)%n,q.push_back(i);
 auto E=[&](int x){if(!v[x]||orient(p[l[x]],p[x],p[r[x]])<=0)return 0;
  range(i,0,n)if(v[i]&&i!=l[x]&&i!=x&&i!=r[x]&&inTri(p[l[x]],p[x],p[r[x]],p[i]))return 0;
  return 1;};
 while(c>3){int x=q.front();q.pop_front();if(!E(x))continue;
  int L=l[x],R=r[x];z.push_back({p[L],p[x],p[R]});
  v[x]=0;r[L]=R;l[R]=L;c--;q.push_back(L);q.push_back(R);}
 range(i,0,n)if(v[i]){z.push_back({p[i],p[r[i]],p[r[r[i]]]});break;}
 return z;
}

// 快捷CV处
// vector<int> a(n, 0);
// vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
void solve() {
	int n; cin >> n;
	vector<pt> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i].x; cin >> a[i].y;
	}
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}