[HNOI2008] 洛谷P3194 水平可见直线

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N=50005;
const double eps=1e-12;
int n,ans[N];
struct Point{double x,y;};
struct Line{Point s,e; int id;}a[N],q[N];

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.x*t,a.y*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+n+1,cmp);
  int h=1, t=1; q[1]=a[1];
  for(int i=2; i<=n; 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++) ans[k++]=q[i].id;
  sort(ans,ans+k);
  for(int i=0;i<k;i++) printf("%d ",ans[i]);
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    double A,B;
    scanf("%lf%lf",&A,&B);
    a[i]={{0,B},{1,A+B},i}; //指向偏右方
  }
  half_plane();
  return 0;
}

【超多图！笔记】[HNOI2008] 洛谷P3194 水平可见直线 [半平面交]-CSDN博客

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

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=50005;
const double eps=1e-12;
int n,ans[N];
struct Point{double x,y;};
struct Line{Point s,e; int id;}a[N],q[N];
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+n+1,cmp);
int h=1, t=1; q[1]=a[1];
for(int i=2; i<=n; 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++) ans[k++]=q[i].id;
sort(ans,ans+k);
for(int i=0;i<k;i++) printf("%d ",ans[i]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
double A,B;
scanf("%lf%lf",&A,&B);
a[i]={{0,B},{1,A+B},i}; //指向偏右方
}
half_plane();
return 0;
}