比赛 “Asm.Def战记之太平洋”杯 评测结果 AAAAAAATTT
题目名称 Asm.Def的一秒 最终得分 70
用户昵称 Binary10 运行时间 3.454 s
代码语言 C++ 内存使用 1.43 MiB
提交时间 2015-11-02 11:47:29
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
struct Point{
  int x, y;
  bool operator < (const Point& rhs) const{
    if(x == rhs.x) return y < rhs.y;
    return x < rhs.x;
  }
}p[maxn];
int a, b, c, d, n, ans = 0, f[maxn];
double k1, k2;
int dfs(int u){
  if(f[u] != -1) return f[u];
  int t = 0;
  for(int i = u + 1; i <= n; i++){
    double k = (double)(p[u].y - p[i].y) / (p[u].x - p[i].x);
    if(k1 < k && k < k2) t = max(t, dfs(i));
  }
  return f[u] = t + 1;
}
int main()
{
  freopen("asm_second.in", "r", stdin);
  freopen("asm_second.out", "w", stdout);
  scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
  k1 = (double)a / b;
  if(d == 0) k2 = 1000000000.0;
  else k2 = (double)c / d;
  p[0].x = p[0].y = 0;
  for(int i = 1; i <= n; i++)
    scanf("%d%d", &p[i].x, &p[i].y);
  sort(p + 1, p + 1 + n);
  memset(f, -1, sizeof(f));
  f[0] = dfs(0);
  printf("%d\n", f[0] - 1);
  return 0;
}