专栏文章
P3081 [USACO13MAR] Hill Walk G 题解
P3081题解参与者 3已保存评论 2
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @miqkroca
- 此快照首次捕获于
- 2025/12/04 06:24 3 个月前
- 此快照最后确认于
- 2025/12/04 06:24 3 个月前
前置知识
解法
自边缘处起跳等价于找到与 相交的直线中最大的 。普通的李超线段树不支持删除操作,直接套用貌似很难处理。
观察到若能从 跳跃至 ,则一定有 。以 排序后顺次扫描线加入即可。
需要离散化和动态开点,注意计算函数值的时候要拿原值来算。
代码
CPP#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
const double eps=1e-9,inf=1e18;
struct node
{
int x1,y1,x2,y2,l,r,pos;
bool operator < (const node &another) const
{
return x1<another.x1;
}
}a[100010];
struct line
{
double k,b;
}li[100010];
int b[300010];
double f(int id,double x)
{
return (id==0)?-inf:li[id].k*x+li[id].b;
}
bool cmp(int a,int b,int x)
{
if(f(a,x)-f(b,x)>eps) return true;
if(f(b,x)-f(a,x)>eps) return false;
return a<b;
}
int sx_max(int a,int b,int x)
{
return cmp(a,b,x)==true?a:b;
}
struct LiChao_Tree
{
struct SegmentTree
{
int id;
}tree[1200010];
#define lson(rt) (rt<<1)
#define rson(rt) (rt<<1|1)
void add(int rt,int l,int r,int id)
{
int mid=(l+r)/2;
if(cmp(tree[rt].id,id,b[mid])==false)
{
swap(tree[rt].id,id);
}
if(l==r)
{
return;
}
if(cmp(tree[rt].id,id,b[l])==false)
{
add(lson(rt),l,mid,id);
}
if(cmp(tree[rt].id,id,b[r])==false)
{
add(rson(rt),mid+1,r,id);
}
}
void update(int rt,int l,int r,int x,int y,int id)
{
if(x<=l&&r<=y)
{
add(rt,l,r,id);
return;
}
int mid=(l+r)/2;
if(x<=mid)
{
update(lson(rt),l,mid,x,y,id);
}
if(y>mid)
{
update(rson(rt),mid+1,r,x,y,id);
}
}
int query(int rt,int l,int r,int pos)
{
if(l==r)
{
return tree[rt].id;
}
int mid=(l+r)/2;
if(pos<=mid)
{
return sx_max(tree[rt].id,query(lson(rt),l,mid,pos),b[pos]);
}
else
{
return sx_max(tree[rt].id,query(rson(rt),mid+1,r,pos),b[pos]);
}
}
}T;
int main()
{
// #define Isaac
#ifdef Isaac
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
int n,ans=0,i,j;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
b[++b[0]]=a[i].l=a[i].x1;
b[++b[0]]=a[i].r=a[i].x2-1;
b[++b[0]]=a[i].pos=a[i].x2;
}
sort(b+1,b+1+b[0]);
b[0]=unique(b+1,b+1+b[0])-(b+1);
for(i=1;i<=n;i++)
{
a[i].l=lower_bound(b+1,b+1+b[0],a[i].l)-b;
a[i].r=lower_bound(b+1,b+1+b[0],a[i].r)-b;
a[i].pos=lower_bound(b+1,b+1+b[0],a[i].pos)-b;
}
sort(a+2,a+1+n);
for(i=1;i<=n;i++)
{
li[i].k=1.0*(a[i].y2-a[i].y1)/(a[i].x2-a[i].x1);
li[i].b=a[i].y1-li[i].k*a[i].x1;
}
for(i=1,j=2;i!=0;i=T.query(1,1,b[0],a[i].pos))
{
ans++;
for(;j<=n&&a[j].x1<=a[i].x2;j++)
{
if(a[j].x2>a[i].x2&&f(j,a[i].x2)<=a[i].y2)
{
T.update(1,1,b[0],a[j].l,a[j].r,j);
}
}
}
cout<<ans<<endl;
return 0;
}
相关推荐
评论
共 2 条评论,欢迎与作者交流。
正在加载评论...