首页 > 代码库 > BZOJ 2732 HNOI 2012 射箭 半平面交
BZOJ 2732 HNOI 2012 射箭 半平面交
题目大意:给出一些与x轴垂直的线段,问一个经过原点的抛物线最多能按顺序经过多少条线段。
思路:总体上来说是数学题,我们来推一推。
设这个经过原点的抛物线为y = a * x ^ 2 + b * x,设一条线段的起点和终点为(x0,y1)和(x0,y2),且y2 > y1。
将x0带入到设出的抛物线中,会得到y = a * x0 ^ 2 + b * x0,这时候需要满足的是y <= y2 && y >= y1,也就是a * x0 ^ 2 + b * x0 <= y2 && y1 <= a * x0 ^ 2 + b * x0
整理一下思路,x0,y1,y2是已知量,a和b是我们设出来的量,不妨换一种写法,令x = a,y = b,k = x0,那么原不等式组就是
=> x * k ^ 2 + y * k <= y2 && x * k ^ 2 + y * k >= y1
=> x * k ^ 2 + y * k - y2 <= 0 && x * k ^2 + y * k - y1 >= 0
这样就很明显了,不等式组化成了两个半平面,之后利用半平面交判定是否存在就可以了。最外层套一个二分,时间复杂度大概是O(nlog^2n)
注意:此题卡精度,亲测1e-10会wa两个点,要1e-11以上才可以AC,同时一条直线的方向向量也要扩大n倍,否则就是被卡,别问我为什么,去给出题人寄刀片!
CODE:
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 200010 #define EPS 1e-15 #define DCMP(a) (fabs(a) < EPS) using namespace std; struct Point{ double x,y; Point(double _ = .0,double __ = .0):x(_),y(__) {} Point operator +(const Point &a)const { return Point(x + a.x,y + a.y); } Point operator -(const Point &a)const { return Point(x - a.x,y - a.y); } Point operator *(double a)const { return Point(x * a,y * a); } }p[MAX]; struct Line{ Point p,v; double alpha; Line(Point _,Point __):p(_),v(__) { alpha = atan2(v.y,v.x); } Line() {} bool operator <(const Line &a)const { return alpha < a.alpha; } }src[MAX],line[MAX],q[MAX]; int asks; int lines; inline double Cross(const Point &p1,const Point &p2) { return p1.x * p2.y - p1.y * p2.x; } inline bool OnLeft(const Point &p,const Line &l) { return Cross(l.v,p - l.p) >= 0; } inline Point GetIntersection(const Line &l1,const Line &l2) { Point u = l1.p - l2.p; double temp = Cross(l2.v,u) / Cross(l1.v,l2.v); return l1.p + l1.v * temp; } inline bool HalfplaneIntersection(int lines) { int front = 1,tail = 1; q[1] = line[1]; for(int i = 2; i <= lines; ++i) { while(front < tail && !OnLeft(p[tail - 1],line[i])) --tail; while(front < tail && !OnLeft(p[front],line[i])) ++front; if(DCMP(Cross(q[tail].v,line[i].v))) q[tail] = OnLeft(q[tail].p,line[i]) ? q[tail]:line[i]; else q[++tail] = line[i]; if(front < tail) p[tail - 1] = GetIntersection(q[tail],q[tail - 1]); } while(front < tail && !OnLeft(p[tail - 1],q[front])) --tail; return tail - front > 1; } inline bool Judge(int mid) { mid <<= 1; memcpy(line + 1,src + 1,sizeof(Line) * mid); sort(line + 1,line + mid + 1); return HalfplaneIntersection(mid); } int main() { cin >> asks; for(int i = 1; i <= asks; ++i) { static double x,y1,y2; scanf("%lf%lf%lf",&x,&y1,&y2); src[++lines] = Line(Point(0,y2 / x),Point(-1 / x,1)); src[++lines] = Line(Point(0,y1 / x),Point(1 / x,-1)); } int l = 1,r = asks,ans = 1; while(l <= r) { int mid = (l + r) >> 1; if(Judge(mid)) ans = mid,l = mid + 1; else r = mid - 1; } cout << ans << endl; return 0; }
BZOJ 2732 HNOI 2012 射箭 半平面交
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。