给你\(2n(1 \leq n \leq 1500)\)个三元组，\(( a_i , b_i , c_i )\)，其中\(a\)，\(b\)是\(10^6\)以内的正整数，\(c\)是(或)
你需要判断，是否存在一组\((x,y)\)，使得将三元组按照\(a_ix+b_iy\)从小到大排序后（相等可以选择随意排序），能否使得括号序列\(c_1\)，\(c_2\)，...，\(c_{2n}\)合法
首先，三元组序列实际上是和\(\frac{x}{y}\)有关，接下来我们不难发现，对于任意两个三元组都只有两种情况
- 两者大小关系为大于，小于或者等于恒成立
- 大小关系随\(\frac{x}{y}\)的变化而变化，存在某个临界点使得两者相等，而临界点上下的不等关系相反
\(n \leq 1500\)，那么一共最多存在\(n^2\)个临界点，同时每个临界点需要考虑的不等关系个数的总和也是\(n^2\)，复杂度合理那么我们以此继续思考
将三元组先按照\(\{ a , b , c \}\)排序，此时\(\frac{x}{y}\)处于极大状态，然后从大到小遍历临界点，每到达一个临界点，我们进行两次排序操作
- 首先考虑将所有以此为临界点的三元组对先按照\(c\)排列，即\(\frac{x}{y}\)取值为当前临界点时恰好相等的值，并将
(排在)前，操作完后判断序列是否合法 - 再考虑将所有以此为临界点的三元组按照\(\frac{x}{y}\)较临界点略小的情况排序，以满足后续条件
序列合法性用线段树判断即可，排序可以考虑直接对点对进行两两交换，但是为了防止出现交换错位而使得某些(被换到等值的)后面，需要对该临界点的三元组进行排序，优先进行在序列中相对靠后的元素的交换
只要存在某个时刻合法，那么答案即为\(Yes\)
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&-x)
using namespace std;
int n,ans,qq,tt;
int a[3005],b[3005],c[3005],p[3005],sum[3005],l[3005];
double now;
vector<pair<double,pair<int,int>>>s;
vector<pair<int,int>>t;
int tree[3005<<2],tag[3005<<2];
const double eps=1e-6;
inline void push_up(int u){
tree[u]=min(tree[u*2],tree[u*2+1]);
}
inline void push_down(int u){
tree[u*2]+=tag[u];
tree[u*2+1]+=tag[u];
tag[u*2]+=tag[u];
tag[u*2+1]+=tag[u];
tag[u]=0;
}
inline void build(int u,int l,int r){
tag[u]=0;
if(l==r){
tree[u]=sum[l];
return;
}
build(u*2,l,l+r>>1);
build(u*2+1,l+r+2>>1,r);
push_up(u);
}
inline void add(int u,int l,int r,int L,int R,int k){
if(k==0)return;
if(l>R||r<L)return;
if(l>=L&&r<=R){
tree[u]+=k;
tag[u]+=k;
return;
}
push_down(u);
add(u*2,l,l+r>>1,L,R,k);
add(u*2+1,l+r+2>>1,r,L,R,k);
push_up(u);
}
inline void change(int x,int y){
x=l[x];y=l[y];
if(y<x)swap(x,y);
add(1,1,n,x,y-1,c[p[y]]-c[p[x]]);
swap(p[x],p[y]);
l[p[x]]=x;l[p[y]]=y;
}
bool cmp1(int x,int y){
if(a[x]!=a[y])return a[x]<a[y];
if(b[x]!=b[y])return b[x]<b[y];
return c[x]>c[y];
}
bool cmp(pair<int,int>x,pair<int,int>y){
int xx,yy;
xx=max(l[x.first],l[x.second]);
yy=max(l[y.first],l[y.second]);
if(xx!=yy)return xx>yy;
xx=min(l[x.first],l[x.second]);
yy=min(l[y.first],l[y.second]);
return xx>yy;
}
void solve(){
s.clear();ans=0;
scanf("%d",&n);n*=2;
for(int i=1;i<=n;i++){
char cc;
scanf("%d%d %c",&a[i],&b[i],&cc);
if(cc=='(')c[i]=1;
else c[i]=-1;
p[i]=i;
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
if(a[i]>=a[j]&&b[i]>=b[j])continue;
if(a[i]<=a[j]&&b[i]<=b[j])continue;
s.push_back({(double)(b[j]-b[i])/(a[i]-a[j]),{i,j}});
if(c[i]<c[j])swap(s.back().second.first,s.back().second.second);
}
sort(s.begin(),s.end());
sort(p+1,p+n+1,cmp1);
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+c[p[i]];
l[p[i]]=i;
}
build(1,1,n);
if(tree[1]>=0)ans=1;
while(!s.empty()&&(!ans)){
t.clear();
now=s.back().first;
while(!s.empty()&&(now==s.back().first)){
t.push_back(s.back().second);
s.pop_back();
}
sort(t.begin(),t.end(),cmp);
for(auto i:t)
if(l[i.first]>l[i.second]&&c[i.first]>c[i.second])
change(i.first,i.second);
if(tree[1]>=0)ans=1;
sort(t.begin(),t.end(),cmp);
for(auto i:t){
int x,y;
x=min(l[i.first],l[i.second]);
y=max(l[i.first],l[i.second]);
x=p[x];y=p[y];
if(b[x]>b[y])change(x,y);
}
}
if(ans)puts("Yes");
else puts("No");
}
int main(){
int t=1;
scanf("%d",&t);
while(t--)solve();
return 0;
}