题目大意:
题解:
这道题的做法我不想说什么了。。。
其他题解都有说做法。。。
即使是我上午做的题,晚上写的题解
看到这道题我就感觉到累.
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 210010;
const long double eps = 1e-18;
inline int dcmp(const long double &x){
if(x < eps && x > -eps) return 0;
return x > 0 ? 1 : -1;
}
struct Point{
long double x,y;
Point(){}
Point(const long double &a,const long double &b){
x=a;y=b;
}
};
typedef Point Vector;
Vector operator + (const Vector &a,const Vector &b){
return Vector(a.x+b.x,a.y+b.y);
}
Vector operator - (const Vector &a,const Vector &b){
return Vector(a.x-b.x,a.y-b.y);
}
Vector operator * (const Vector &a,const long double &b){
return Vector(a.x*b,a.y*b);
}
long double cross(const Vector &a,const Vector &b){
return a.x*b.y - a.y*b.x;
}
struct line{
Point p;
Vector v;
long double alpha;
int id;
line(){}
line(const Point &a,const Point &b,int i){
p = a;v = b;id = i;
alpha = atan2(v.y,v.x);
// printf("(%lf,%lf) got %lf
",v.x,v.y,alpha);
}
};
Point lineInterion(const line &l1,const line &l2){
Vector u = l1.p - l2.p;
long double t = cross(l2.v,u)/cross(l1.v,l2.v);
return l1.p + l1.v*t;
}
bool onLeft(const Point &p,const line &l){
return dcmp(cross(l.v,p-l.p)) >= 0;
}
inline bool cmp(const line &a,const line &b){
return a.alpha < b.alpha;
}
line lines[maxn],q[maxn];
Point p[maxn];
int l,r;
inline bool halfInterion(int n){
l = 1;r = 1;q[1] = lines[1];
for(int i=2;i<=n;++i){
while(l < r && !onLeft(p[r-1],lines[i])) -- r;
while(l < r && !onLeft(p[l],lines[i])) ++ l;
if(dcmp(cross(q[r].v,lines[i].v)) == 0)
q[r] = onLeft(q[r].p,lines[i]) ? q[r] : lines[i];
else q[++r] = lines[i];
if(l < r) p[r-1] = lineInterion(q[r],q[r-1]);
}while(l < r && !onLeft(p[r-1],q[l])) -- r;
return (r-l > 1);
}
line a[maxn];
int n,cnt = 0,tot;
inline bool check(int mid){
tot = 0;
for(int i=1;i<=cnt;++i){
if(a[i].id > mid) break;
tot = i;
lines[i] = a[i];
}
sort(lines+1,lines+tot+1,cmp);
return halfInterion(tot);
}
const long double inf = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000.0;
int main(){
read(n);
double v,L,R;
a[++cnt] = line(Point(-inf,-inf),Point(inf,0),0);
a[++cnt] = line(Point(inf,-inf),Point(0,inf),0);
a[++cnt] = line(Point(inf,inf),Point(-inf,0),0);
a[++cnt] = line(Point(-inf,inf),Point(0,-inf),0);
for(int i=1;i<=n;++i){
scanf("%lf%lf%lf",&v,&L,&R);
L -= eps;R += eps;
a[++cnt] = line(Point(0,R/v),Point(-1/v,1),i);
a[++cnt] = line(Point(0,L/v),Point(1/v,-1),i);
}
int l = 1,r = n,ans = 0;
while(l <= r){
int mid = (l+r) >> 1;
if(check(mid)) ans = mid,l = mid+1;
else r = mid-1;
}printf("%d
",ans);
getchar();getchar();
return 0;
}
。。。 。。。
下面的那个Ac是粘的hzwer的代码...最上面的才是自己A的
