比赛 “Asm.Def战记之太平洋”杯 评测结果 WWWWWWTTTT
题目名称 Asm.Def的一秒 最终得分 0
用户昵称 fengchenxue 运行时间 4.323 s
代码语言 C++ 内存使用 4.89 MiB
提交时间 2015-11-02 10:47:50
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<cstring>
#include<string>
#include<cstdlib>
using namespace std;
vector<int> q[100010];
int n;
double kx,ks;
double xx,xy,sx,sy;
struct str{
	double bx,bs,x,y;
	int num;
}f[100010];
int fun(int b,int a)
{
	int m,maxx;
	if(f[a].num) return f[a].num;
	f[a].bx=f[a].y-f[a].x*kx;
	f[a].bs=f[a].y-f[a].x*ks;
	for(int i=0;i<q[b].size();i++)
	{
		m=q[b][i];
		if(f[m].y-kx*f[m].x-f[a].bx<=0||f[m].y-ks*f[m].x-f[a].bs>=0) continue;
		q[a].push_back(m);
	}
	if(q[a].empty()==1)
	{
		f[a].num=1;
		return 1;
	}
	for(int i=0;i<q[a].size();i++)
	{
		maxx=max(maxx,fun(a,q[a][i]));
	}
	f[a].num=maxx+1;
	return f[a].num;
	
}
int main()
{

freopen("asm_second.in", "r", stdin);
	freopen("asm_second.out", "w", stdout); 
	cin>>n;
	cin>>xy>>xx>>sy>>sx;
	 kx=xy/xx,ks=sy/sx;
	for(int i=1;i<=n;i++)
	{
		cin>>f[i].x>>f[i].y;
		if(f[i].y-kx*f[i].x<=0||f[i].y-ks*f[i].x>=0) continue;
		q[0].push_back(i);
	}
	int maxx=0;
	for(int i=0;i<q[0].size();i++)
	{
		maxx=max(maxx,fun(0,q[0][i]));
	}
	cout<<maxx;
	return 0;
	

}