记录编号	147658	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]水平可见直线	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.096 s
提交时间	2015-02-02 20:28:47	内存使用	0.89 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x3fffffff;
const double PI=3.1415926535897932;
const double eps=1e-10;
//==============struct declaration==============
struct Points{
  double x,y;
  Points(double x=0,double y=0):x(x),y(y){}
  Points operator +(const Points &rhs)const{
    return Points(x+rhs.x,y+rhs.y);
  }
  Points operator *(const double &Mul) const{
    return Points(x*Mul,y*Mul);
  }
  Points operator -(const Points &rhs) const{
    return (*this)+rhs*-1;
  }
};
struct Lines{
  int No;
  int K,B;
  bool operator <(const Lines &rhs) const{
    return K<rhs.K;
  } 
};
//==============var declaration=================
const int MAXN=50010;
int n;
Lines line[MAXN];
deque <Lines> LineQ;
deque <Points> PointQ;
//==============function declaration============
Points GetIntersection(Lines L1,Lines L2);
bool Onleft(Lines L,Points P);
//==============main code=======================
int main()
{  
#define FILE__
#ifdef FILE__
  freopen("bzoj_1007.in","r",stdin);
  freopen("bzoj_1007.out","w",stdout);
#endif  
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    line[i].No=i;
    scanf("%d%d",&line[i].K,&line[i].B);
  }
  sort(line+1,line+1+n);
  LineQ.push_back(line[1]);
  for(int i=2;i<=n;i++){
    if (line[i].K==LineQ.back().K){
      if (line[i].B>LineQ.back().B){
        LineQ.pop_back();
        if (!PointQ.empty())
          PointQ.pop_back();
      }
      else 
        continue;
    }
    while (!PointQ.empty()&&!LineQ.empty()&&!Onleft(line[i],PointQ.back())){
      LineQ.pop_back();
      PointQ.pop_back();
    }
    if (!LineQ.empty())
      PointQ.push_back(GetIntersection(line[i],LineQ.back()));
    LineQ.push_back(line[i]);
  }
  vector <int >visible;
  for(deque <Lines> ::iterator it=LineQ.begin();it!=LineQ.end();++it)
    visible.push_back(it->No);
  sort(visible.begin(),visible.end());
  for(int i=0;i<visible.size();i++)
    printf("%d ",visible[i]);
  return 0;
}
//================fuction code====================
Points GetIntersection(Lines L1,Lines L2){
  double k1=L1.K,k2=L2.K,b1=L1.B,b2=L2.B;
  double x=(b1-b2)/(k2-k1);
  double y=L1.K*x+L1.B;
  return Points(x,y);
}
bool Onleft(Lines L,Points P){
  double stdy=L.K*P.x+L.B;
  return stdy-P.y<=-eps;
}