历史遗留问题，，，
发现是原题之后我就去单切了，因为我没打过去年的宁夏，两个队友都打了。。
然后就被这个题治死了。
其实思路挺好想的，就是分一下两边的点，然后找一个字典序最小的二维严格上升子序列就行了。
坐标范围显然不可能用atan2什么的就不用说了(被18北京K治成傻逼的回忆很深刻)
嗯...然后我把前面搞完了，要找 字典序最小的二维上升子序列，嗯....
我不想施展树状数组，然后脑补了好久
想！到！了！一！个！绝！妙！的！二！分！方！法！
然后我去搞了三五天数据库课设就忘了怎么做了
？？？？？？？？
nmd然后就一直拖到现在，晚上刚睡晚课感觉比较清醒就补了补
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
struct BIT {
int a[N], n;
inline void init(int _n) { n = _n; memset(a, 0, sizeof (a[0]) * (n + 10)); }
inline int lowbit(int x){return x&-x;}
inline void update(int pos,int x){
while (pos<=n)a[pos]=max(a[pos],x),pos+=lowbit(pos);
}
inline int query(int pos){
int res=0;
while (pos)res=max(res,a[pos]),pos-=lowbit(pos);
return res;
}
}bit;
struct point{
ll x,y;int id,id1,id2;
point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
};
ll cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
int t,n;point a,b;
point p[100005];
vector<point> v1,v2;
bool cmp1(point x,point y){return cross(x-a,y-a)<0;}
bool cmp2(point x,point y){return cross(x-b,y-b)>0;}
int f[100005];
vector<vector<int>> ord;
vector<int> slove1(){//a->b 右边的
if(v1.empty())return {};
sort(v1.begin(),v1.end(),cmp1);//按照a递减
int ind=1;
for(int l=0,r=l;l<v1.size();l=r+1,r=l,ind++){
while (r+1<v1.size()&&cross(v1[r+1]-a,v1[l]-a)==0)r++;
for(int i=l;i<=r;i++)v1[i].id1=ind;
}
sort(v1.begin(),v1.end(),cmp2);
ind=1;
for(int l=0,r;l<v1.size();l=r+1,ind++){
r=l;
while (r+1<v1.size()&&cross(v1[r+1]-b,v1[l]-b)==0)r++;
for(int i=l;i<=r;i++)v1[i].id2=ind;
}
sort(v1.begin(), v1.end(), [&](point x, point y){
if (x.id1!= y.id1) return x.id1 < y.id1;
return x.id2 > y.id2;
});
bit.init(n);
int mx = 0;
for(int i=0;i<v1.size();i++){
f[i] = bit.query(v1[i].id2 - 1) + 1;
bit.update(v1[i].id2, f[i]);
mx = max(mx, f[i]);
}
ord.clear();ord.resize(mx+10);
for(int i=0;i<v1.size();i++){
ord[f[i]].push_back(i);
}
vector<int> ans;
int pos = v1.size();
for(int i=mx;i>=1;i--){
int now=-1;
for (auto it : ord[i]) {
if (pos == v1.size() || (v1[it].id1 < v1[pos].id1 && v1[it].id2 < v1[pos].id2)) {
if (now == -1 || v1[it].id < v1[now].id) {
now = it;
}
}
}
pos = now;
ans.push_back(v1[now].id);
}
return ans;
}
bool cmp3(point x,point y){return cross(x-a,y-a)>0;}
bool cmp4(point x,point y){return cross(x-b,y-b)<0;}
vector<int> slove2(){
if(v2.empty())return {};
sort(v2.begin(),v2.end(),cmp3);//按照a递减
int ind=1;
for(int l=0,r=l;l<v2.size();l=r+1,r=l,ind++){
while (r<v2.size()&&cross(v2[r+1]-a,v2[l]-a)==0)r++;
for(int i=l;i<=r;i++)v2[i].id1=ind;
}
sort(v2.begin(),v2.end(),cmp4);//按照b递减
ind=1;
for(int l=0,r=l;l<v2.size();l=r+1,r=l,ind++){
while (r+1<v2.size()&&cross(v2[r+1]-b,v2[l]-b)==0)r++;
for(int i=l;i<=r;i++)v2[i].id2=ind;
}
sort(v2.begin(), v2.end(), [&](point x, point y){
if (x.id1!= y.id1) return x.id1 < y.id1;
return x.id2 > y.id2;
});
bit.init(n);
int mx = 0;
for(int i=0;i<v2.size();i++){
f[i] = bit.query(v2[i].id2 - 1) + 1;
bit.update(v2[i].id2, f[i]);
mx = max(mx, f[i]);
}
ord.clear();ord.resize(mx+10);
for(int i=0;i<v2.size();i++){
ord[f[i]].push_back(i);
}
vector<int> ans;
int pos = v2.size();
for(int i=mx;i>=1;i--){
int now=-1;
for (auto it : ord[i]) {
if (pos == v2.size() || (v2[it].id1 < v2[pos].id1 && v2[it].id2 < v2[pos].id2)) {
if (now == -1 || v2[it].id < v2[now].id) {
now = it;
}
}
}
pos = now;
ans.push_back(v2[now].id);
}
return ans;
}
void prt(vector<int> v){
for(auto x:v)cout<<x<<'
';
}
vector<int> w,s,m,l;
int main(){
scanf("%d",&t);
int cas = 0;
while (t--){
v1.clear();
v2.clear();
cas++;
scanf("%lld%lld",&a.x,&a.y);
scanf("%lld%lld",&b.x,&b.y);
if(a.y>b.y)swap(a,b);
if(a.y==b.y&&a.x>b.x)swap(a,b);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&p[i].x,&p[i].y);p[i].id=i;
if(cross(p[i]-a,b-a)>0){//
v1.push_back(p[i]);
}else if(cross(p[i]-a,b-a)<0){
v2.push_back(p[i]);
}
}
s=slove1();
w=slove2();
printf("Case #%d: %d
", cas, (int) max(w.size(), s.size()));
if (s.size() == w.size()) {
if (s[0] < w[0]) {
prt(s);
} else {
prt(w);
}
} else if (s.size() < w.size())prt(w);
else prt(s);
}
}