https://blog.csdn.net/tenkuo/article/details/150467413?spm=1001.2014.3001.5502

G54 半平面交 双端队列【计算几何】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#define double long double //交点坐标很大
using namespace std;

const int N=10010;
const double eps=1e-18;
struct Point{double x,y;};
struct Line{
  Point s,e; vector<int> id; //这条直线对应的所有赛车
}a[N],q[N];
int n,cnt,k[N],v[N],ans[N];
map<pair<int, int>, vector<int>> mp;

Point operator+(Point a,Point b){ //向量+
  return {a.x+b.x,a.y+b.y};
}
Point operator-(Point a,Point b){ //向量-
  return {a.x-b.x,a.y-b.y};
}
Point operator*(Point a,double t){ //数乘
}
double operator*(Point a,Point b){ //叉积
  return a.x*b.y-a.y*b.x;
}
double angle(Line& a){ //极角(-Pi,Pi]
  return atan2(a.e.y-a.s.y, a.e.x-a.s.x);
}
bool cmp(Line& a, Line& b){ //按极角+左侧排序
  double A=angle(a), B=angle(b);
  return fabs(A-B)>eps ? A<B : (a.e-a.s)*(b.e-a.s)<0;
}
Point cross(Line& a,Line& b){ //直线交点
  Point u=a.s-b.s, v=a.e-a.s, w=b.e-b.s;
  double t=u*w/(w*v);
  return a.s+v*t;
}
bool right(Line& a,Line& b,Line& c){//交点在右侧
  Point p=cross(b,c);
  return (a.e-a.s)*(p-a.s)<0;
}
void half_plane(){ //半平面交
  sort(a+1,a+cnt+1,cmp);
  int h=1, t=1; q[1]=a[1];
  for(int i=2; i<=cnt; i++){ //枚举直线
    if(angle(a[i])-angle(a[i-1])<eps)continue;
    while(h<t && right(a[i],q[t],q[t-1]))t--;
    //while(h<t && right(a[i],q[h],q[h+1]))h++;
    q[++t]=a[i];
  }
  int k=0;
  for(int i=h;i<=t;i++){
    for(int id: q[i].id) ans[++k]=id;
  }
  sort(ans+1, ans+k+1);  printf("%d\n", k);
  for(int i=1;i<=k;i++) printf("%d ", ans[i]);
}
int main(){
  scanf("%d", &n);
  for(int i=1;i<=n;i++) scanf("%d", &k[i]);
  for(int i=1;i<=n;i++) scanf("%d", &v[i]);
  for(int i=1;i<=n;i++) mp[{v[i],k[i]}].push_back(i);
  a[++cnt]={{0,1},{0,0}}; //补负y轴
  for(auto &[b,c]:mp)     //{(0,k),(1,v+k),i}
    a[++cnt]={{0,b.second},{1,b.first+b.second},c};
  half_plane();
}

https://blog.csdn.net/tenkuo/article/details/150467413?spm=1001.2014.3001.5502

G54 半平面交 双端队列【计算几何】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#define double long double //交点坐标很大
using namespace std;
const int N=10010;
const double eps=1e-18;
struct Point{double x,y;};
struct Line{
Point s,e; vector<int> id; //这条直线对应的所有赛车
}a[N],q[N];
int n,cnt,k[N],v[N],ans[N];
map<pair<int, int>, vector<int>> mp;
Point operator+(Point a,Point b){ //向量+
return {a.x+b.x,a.y+b.y};
}
Point operator-(Point a,Point b){ //向量-
return {a.x-b.x,a.y-b.y};
}
Point operator*(Point a,double t){ //数乘
return {a.xt,a.yt};
}
double operator*(Point a,Point b){ //叉积
return a.xb.y-a.yb.x;
}
double angle(Line& a){ //极角(-Pi,Pi]
return atan2(a.e.y-a.s.y, a.e.x-a.s.x);
}
bool cmp(Line& a, Line& b){ //按极角+左侧排序
double A=angle(a), B=angle(b);
return fabs(A-B)>eps ? A<B : (a.e-a.s)(b.e-a.s)<0;
}
Point cross(Line& a,Line& b){ //直线交点
Point u=a.s-b.s, v=a.e-a.s, w=b.e-b.s;
double t=uw/(wv);
return a.s+vt;
}
bool right(Line& a,Line& b,Line& c){//交点在右侧
Point p=cross(b,c);
return (a.e-a.s)*(p-a.s)<0;
}
void half_plane(){ //半平面交
sort(a+1,a+cnt+1,cmp);
int h=1, t=1; q[1]=a[1];
for(int i=2; i<=cnt; i++){ //枚举直线
if(angle(a[i])-angle(a[i-1])<eps)continue;
while(h<t && right(a[i],q[t],q[t-1]))t--;
//while(h<t && right(a[i],q[h],q[h+1]))h++;
q[++t]=a[i];
}
int k=0;
for(int i=h;i<=t;i++)
for(int id: q[i].id) ans[++k]=id;
sort(ans+1, ans+k+1);  printf("%d\n", k);
for(int i=1;i<=k;i++) printf("%d ", ans[i]);
}
int main(){
scanf("%d", &n);
for(int i=1;i<=n;i++) scanf("%d", &k[i]);
for(int i=1;i<=n;i++) scanf("%d", &v[i]);
for(int i=1;i<=n;i++) mp[{v[i],k[i]}].push_back(i);
a[++cnt]={{0,1},{0,0}}; //补负y轴
for(auto &[b,c]:mp)     //{(0,k),(1,v+k),i}
a[++cnt]={{0,b.second},{1,b.first+b.second},c};
half_plane();
}