用的网上的半平面交的板子写的
但这题是一道比较毒瘤的题,卡精度的同时,还卡范围
对策:无脑开$long$ $double$,INF设置成$1e^{50}$
思路
这道题跟HDU2297比较相似,不太一样的是,要小到大的顺序输出获奖赛车的编号
所以我一直在思考如何用板子套进去做(
方法:找到半平面交后的凸包点集,再枚举每条线,再枚举凸包点集,判断点是否在线上,如果在就保存线的id
这道题就愉快得解决了(3 hours) mmp
#include <bits/stdc++.h>
using namespace std;
#define double long double
const double INF = 1e50;
const double pi = acos(-1.0);
const double eps = 1e-8;
int sgn(double x)
{
if(fabs(x) < eps) return 0;
else return x<0?-1:1;
}
struct Point
{
double x,y;
Point() {}
Point(double x,double y):x(x),y(y) {}
Point operator + (Point B)
{
return Point(x+B.x,y+B.y);
}
Point operator - (Point B)
{
return Point(x-B.x,y-B.y);
}
Point operator * (double k)
{
return Point(x*k,y*k);
}
};
typedef Point Vector;
double Cross(Vector A,Vector B)
{
return A.x*B.y - A.y*B.x; //叉积
}
struct Line
{
int id;
Point p;
Vector v;
double ang;
Line() {};
Line(Point p,Vector v,int id):p(p),v(v),id(id)
{
ang=atan2(v.y,v.x);
}
bool operator < (Line &L)
{
return ang<L.ang; //用于极角排序
}
double value(double x)
{
return p.y+(x-p.x)*v.y/v.x;
}
};
//点p在线L左边,即点p在线L在外面:
bool OnLeft(Line L,Point p)
{
return sgn(Cross(L.v,p-L.p))>0;
}
Point Cross_point(Line a,Line b) //两直线交点
{
Vector u=a.p-b.p;
double t=Cross(b.v,u)/Cross(a.v,b.v);
return a.p+a.v*t;
}
vector<Point> HPI(vector<Line> &L) //求半平面交,返回图多边形
{
int n=L.size();
sort(L.begin(),L.end());//将所有半平面按照极角排序。
int first,last; //指向双端队列的第一个和最后一个元素
vector<Point> p(n); //两个相邻半平面的交点
vector<Line> q(n); //双端队列
vector<Point> ans; //半平面交形成的凸包
q[first=last=0]=L[0];
for(int i=1; i<n; i++)
{
//情况1:删除尾部的半平面
while(first<last && !OnLeft(L[i], p[last-1])) last--;
//情况2:删除首部的半平面:
while(first<last && !OnLeft(L[i], p[first])) first++;
q[++last]=L[i]; //将当前的半平面加入双端队列尾部
//极角相同的两个半平面,保留左边:
if(fabs(Cross(q[last].v,q[last-1].v)) < eps)
{
last--;
if(OnLeft(q[last],L[i].p)) q[last]=L[i];
}
//计算队列尾部半平面交点:
if(first<last) p[last-1]=Cross_point(q[last-1],q[last]);
}
//情况3:删除队列尾部的无用半平面
while(first<last && !OnLeft(q[first],p[last-1])) last--;
if(last-first<=1) return ans; //空集
p[last]=Cross_point(q[last],q[first]); //计算队列首尾部的交点。
for(int i=first; i<=last; i++) if (p[i].y<INF) ans.push_back(p[i]); //复制。
return ans; //返回凸多边形
}
double Polygon_area(vector<Point> p) //Point *p表示多边形。从原点开始划分三角形
{
int n=p.size();
double area = 0;
for(int i = 0; i < n; i++)
area += Cross(p[i],p[(i+1)%n]);
return area/2; //面积有正负,不能简单地取绝对值
}
int main()
{
int n,m;
vector<Line> L;
vector<double> tmpx;
L.push_back(Line(Point(0, 0), Vector(0, -1), 0));
L.push_back(Line(Point(0, 0), Vector(1, 0), 0));
L.push_back(Line(Point(INF, 0), Vector(0, 1), 0));
L.push_back(Line(Point(0, INF), Vector(-1, 0), 0));
scanf("%d",&n);
for(int i=0; i<n; i++)
{
double xx;
scanf("%llf",&xx);
tmpx.push_back(xx);
}
for(int i=0; i<n; i++)
{
double K;
scanf("%llf",&K);
L.push_back(Line(Point(0,tmpx[i]),Vector(1,K),i+1));
}
vector<Point> ans=HPI(L); //得到凸多边形
//for(auto it:ans) cout<<it.x<<' '<<it.y<<endl;
//return 0;
vector<int> res;
for(int i=0;i<L.size();i++)//枚举每条边
{
if (L[i].id==0) continue;
for(int j=0;j<ans.size();j++)//枚举半平面的凸包点
{
if (!sgn(L[i].value(ans[j].x)-ans[j].y))//用初中的y=k*x+b来计算线上的y值
{
res.push_back(L[i].id);
break;
}
}
}
sort(res.begin(),res.end());
printf("%d\n",res.size());
for(int i=0;i<res.size();i++) printf("%d ",res[i]);
return 0;
}
为什么除了添加两条在x轴y轴的直线外,还另外需要两条无限趋近的直线,是因为精度问题吗,不是很懂