about 4 years ago

初中的数学题,注意double
按斜率由小到大排序
有直线a,b,c
可证明当a与c的交点在b与c的交点之前,b不会被看见。
用栈维护

/**************************************************************
    Problem: 1007
    User: LaVenDer
    Language: C++
    Result: Accepted
    Time:200 ms
    Memory:1592 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define eps 0.0000001
#define maxn 50001
using namespace std;
struct wide
{
    int k,b;int num;
} a[maxn];
int stack[maxn]={0},top=0,n;
int cmp(const wide x,const wide y)
{
    if (x.k!=y.k)return x.k<y.k;
    else return x.b<y.b;
}
double calx(int p,int q)
{
    return  (double)(a[p].b-a[q].b)/(a[q].k-a[p].k);
}
int cmp1(int x,int y)
{
    return a[x].num<a[y].num;
}
void put(int k)
{
    int i,j;
    while (top>1&&calx(stack[top-1],k)<=calx(stack[top],stack[top-1])) top--;
    stack[++top]=k;
}
int main()
{
   scanf("%d",&n);
   for (int i=1;i<=n;i++)scanf("%d%d",&a[i].k,&a[i].b),a[i].num=i;
   sort(a+1,a+n+1,cmp);
   int k=1;
   while (k<=n)
   {
    while (k<n&&a[k].k==a[k+1].k) k++;
       put(k);
       k++;
   }
   sort(stack+1,stack+top+1,cmp1);
   for (int i=1;i<=top;i++)
     printf("%d ",a[stack[i]].num);
}
← 【bzoj3196】【分块】二逼平衡树 【bzoj2957】【线段树】【神做法】楼房重建 →
 
comments powered by Disqus