P4864 Jerry Loves Lines

2018-09-04 19:01:25

$n^2$ 枚举，算出直线的两两交点

（在按照左端函数值排好序的情况下，如果后面直线在最右端的函数值比前面小，则两直线相交）

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=2005,M=5e5+5;
struct line
{
int k,b,id; ll y;
inline friend bool operator < (line a,line b) {return a.y<b.y;}
}c[N];
struct Q
{
int x,id;
inline friend bool operator < (Q a,Q b) {return a.x<b.x;}
}q[M];
struct node
{
int x,y; ll p;
inline friend bool operator < (node a,node b)
{
return a.p==b.p?a.x<b.x:a.p<b.p;
}
}t[2000005];
int n,m,k,cnt,num[N],rk[N];
ll ans[M];
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline ll calc(int x,int k){return (ll)c[k].k*x+c[k].b;}
inline ll getpos(int p,int q){return (ll)(c[q].b-c[p].b)/(c[p].k-c[q].k)+1;}
int main()
{
n=read(),m=read(),k=read();
for (reg int i=1;i<=n;i++) c[i].k=read(),c[i].b=read();
for (reg int i=1;i<=m;i++) q[i].x=read(),q[i].id=i; sort(q+1,q+m+1);
for (reg int i=1;i<=n;i++) c[i].y=calc(q[1].x,i); sort(c+1,c+n+1);
for (reg int i=1;i<=n;i++)
{
c[i].id=num[i]=rk[i]=i;
for (reg int j=i+1;j<=n;j++)
if (c[i].k!=c[j].k&&calc(q[m].x,i)>=calc(q[m].x,j))
{
ll pos=getpos(i,j);
if (pos>=q[1].x) t[++cnt]=(node){i,j,pos};
}
}
sort(t+1,t+cnt+1);
for (reg int i=1,now=1;i<=m;i++)
{
while (now<=cnt&&t[now].p<=q[i].x)
{
num[++rk[t[now].x]]=t[now].x;
num[--rk[t[now].y]]=t[now].y;
++now;
}
ans[q[i].id]=calc(q[i].x,num[k]);
}
for (reg int i=1;i<=m;i++) printf("%lld\n",ans[i]);
return 0;
}
• star
首页