8.18DAY2

Posted on Edited on In

上午

讲了一道与二分有一点关系的题

消防

click

  • 1.要找的路径一定在直径上。

    很容易用反证法证明，只需讨论该路径与直径有交集和无交集的情况。

    若有多条直径，随便讨论一条都行。

  • 2.任意找出一条直径，将直径上的边权值设为0，再BFS一遍，就可以找出所有点到直径的最短距离。

  • 3.从“枢纽路径”到每个点的最大距离有两种情况

    A.枢纽到该点 B.枢纽到直径的端点

  • 4.二分直径两端要去掉的长度。 然后再判断剩余的长度满不满足题目中要求的最大长度。

    二分的下限为所有点到枢纽路径的距离中的最大者

    二分的上限为直径的长度

有一些细节，详见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 3e5+66;

int to[N << 1], nex[N << 1], len[N << 1], head[N << 1], cnt;

inline void add(int x, int y, int z)
{
    to[++ cnt] = y;
    len[cnt] = z;
    nex[cnt] = head[x];
    head[x] = cnt;
}

int dis[N], fa[N], v[N], tot, f[N<<1];

inline void bfs(int now)
{
    memset(dis, -1, sizeof dis);
    queue<int>q; int i, x, y;
    dis[now] = 0, q.push(now);
    while (!q.empty())
    {
        x = q.front(); q.pop();
        for (i = head[x]; i; i = nex[i])
        {
            y = to[i];
            if (dis[y] != -1) continue;
            fa[y] = x;
            if (v[y]) dis[y] = dis[x];
            else dis[y] = dis[x] + len[i];
            //对于前两个bfs，我们都没有用到v，显然这么写是没有问题的
            //而对于第三个bfs，我们的v数组表示，直径上的点的距离都是零(人为规定)
            q.push(y);
        }
    }
}

inline int pd(int mid, int s)
{
    int l = 1, r = tot;
    while (l <= tot && f[1] - f[l + 1] <= mid) ++ l;
    while (r >= 1 && f[r] <= mid) -- r;
    return f[l] - f[r + 1] <= s;
    /*
    while (r >= 1 && f[r + 1] <= mid) -- r;
    return f[l] - f[r] <= s;
    这么写也是可以的
    */
}

inline int thestars()
{
    int i, x, y, z, n, s, From(0), To(0);
    scanf ("%d%d", &n, &s);
    for (i = 1; i < n; ++ i)
    {
        scanf ("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    bfs(1);
    for (i = 1; i <= n; ++ i) if (dis[i] > dis[From]) From = i;
    bfs(From);
    for (i = 1; i <= n; ++ i) if (dis[i] > dis[To]) To = i;
    int d = dis[To];
    f[++ tot] = dis[To]; v[To] = 1;
    while (From != To)
    {
        f[++ tot] = dis[fa[To]];
        To = fa[To];
        v[To] = 1;
    }
    bfs(To);
    int l = 0, r = d, mid;
    for (i = 1; i <= n; ++ i) l = max(l, dis[i]);
    while (l < r)
    {
        mid = (l + r) >> 1;
    //我们尝试在左右两边都减掉mid，然后再判断剩余的长度是否满足题目中要求的长度
        if (pd(mid, s)) r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}

int youngore = thestars();

signed main() {;}

还讲了一些贪心的例题，不是太多，但是我感觉都挺经典的

合并果子

每次选出最小的两个来合并，哈夫曼树？

钓鱼

click

显然无论任何一种做法，都是走一遍的，因为来回走，显然不优

考虑dp

状态：\(f[i][j]\)表示在j个单位时间内，在前i个池塘中最多能钓的鱼数

转移：\(f[i][j] = Max(f[i-1][j],f[i-1][ j-k-walk[i]]+GetFish[i][k])\)

结果：\(f[m][n]\)

考虑贪心

脑子里不由得怎么响起了cjh的毒瘤反问“贪心？怎么贪？搜索？怎么搜？”

由于只能走一边，所以我们考虑对于每一个点都作为终点来跑一边

假设以i号池塘作为终点，那么先用总时间减去从1号池塘到i号池塘行走耗费的时间,\(Fish_Time=h-walk[i]\)，那么剩下的时间(Fish_Time)就是用来钓鱼的时间了。

现在就相当于现在可以在1到i号池塘间任意瞬间移动了，每一个单位时间选当前能够钓到鱼最多的池塘来钓就行了，选最大用大根堆实现。

  • 1.每次从堆顶取出能钓到最大数量鱼的湖，并在那里钓一个单位时间的鱼，将钓到的鱼累加钓鱼的总数上;
  • 2.把该湖下一个单位时间能钓鱼的数量更新(减去di)后，重新存入堆中；
  • 3.总钓鱼时间减去一个单位的时间，重复该过程，直到没有时间或没有鱼可钓了为止;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
int const maxn=10001;
struct node{
    int f,d;
    bool operator <(node x)const{
        return f<x.f;
    }
}a[maxn];
int n,h,i,j,k,d[maxn],t[maxn],ans,H;
priority_queue<node>q;
int main(){
    cin>>n>>H;
    H*=12;
    for(i=1;i<=n;++i)
        cin>>a[i].f;
    for(i=1;i<=n;++i)
        cin>>a[i].d;
    for(i=1;i<n;++i)
        cin>>t[i];
    for(int i=1;i<=n;i++){       
        h=H;
        for(j=1;j<i;j++)h-=t[j];            
        int now=0;
        while(q.size())q.pop();
        for(j=1;j<=i;++j)  
            q.push(a[j]);
        while(h>0){
           node s;
            s=q.top(); 
        q.pop();    
                    
            now+=s.f;    
            s.f-=s.d;   
            if(s.f<0) s.f=0;   
            q.push(s);
            h--;
        }
        ans=max(ans,now);     
    }
    cout<<ans<<endl;
    return 0;
}

黑盒序列

click

黑匣子\(hei\;xia\;zi\)

貌似有很多nb做法，splay，主席树

但是这里我们考虑用一种比较方便的东西来实现——大根堆与小跟堆

假设当前序列有t个数字

把数字都加到大根堆里面去，然后查询的时候，删除大根堆最大的\(t-k+1\)个数字，也就是说，大根堆里面留下了\(k - 1\)个数字

（目前序列的前k-1小的数字）

在上一个步骤里面，把每次删除的数字都压入到小根堆里面，最后小根堆里面就有了\(t-k+1\)个数字，而小根堆的堆首，就是当前第k大的数字，正确性显然

另：大根堆要重载小于号，小根堆重载大于号

防晒霜

click

这次讲的方法我感觉冗杂，不太好，我比较喜欢简单一些的方法

给出一种方便简单的方法：

按照\(Min(SPF)\)递减的顺序排序，依次考虑每一头奶牛，对于每一个奶牛，在这头奶牛能用的防晒霜里面找SPF最大的

考虑贪心证明：考虑这一步的策略的作用范围扩展到后续其他奶牛之后产生的影响，每瓶防晒霜会被最大和最小两个值限制，

因为奶牛已经被按照\(minSPF\)排序了，所以每一个不低于当前奶牛的\(minSPF\)值的防晒霜，都不会小于后面奶牛的\(SPF\),

也就是说，对于当恰奶牛可用的任意两瓶防晒霜x,y，如果发现\(SPF[x] <SPF [y]\)，那么后面奶牛只可能出现“xy都能用”，或者“xy都不能用”，或者“x能用，但是y不能用”，因此当前奶牛选择\(maxSPF\)较大的y去使用，对于整体问题的影响，显然比选择\(maxSPF\)较小的x要更好

另外，每一头奶牛的贡献都是1，即使让当前的奶牛放弃日光浴，留下防晒霜给后面的某一个用，结果不会变的更大

至此，尽量满足当前的奶牛，并选择\(SPF\)值较大的的防晒霜是一个正确的贪心策略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//Author:XuHt
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2506;
int n, m;
struct COW {
    int l, r;
    bool operator < (const COW x) const {
        return l > x.l;
    }
} cow[N];
struct SPF {
    int s, c;
    bool operator < (const SPF x) const {
        return s > x.s;
    }
} spf[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d %d", &cow[i].l, &cow[i].r);
    for (int i = 1; i <= m; i++) scanf("%d %d", &spf[i].s, &spf[i].c);
    sort(cow + 1, cow + n + 1);
    sort(spf + 1, spf + m + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (spf[j].c && spf[j].s >= cow[i].l && spf[j].s <= cow[i].r) {
                ans++;
                spf[j].c--;
                break;
            }
    cout << ans << endl;
    return 0;
}

植物大战僵尸

click

下午

讲了一些倍增的东西

跑路

click

一道写的我自信心爆棚的题，随手切一道绿题

我们记录两个数组：

\(f[i][j][k]\)表示是否有一条道路从\(i\)经过\(2^k\)到达\(j\)

\(g[i][j]\)表示两个之间的距离

考虑转移：\(f[i][k][t- 1]\) && \(f[k][j][t-1]\)

但是GXZ大佬说过，RP守恒……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 55;

int f[N][N][N], g[N][N];

inline int thestars()
{
    memset(g, 0x3f, sizeof g);
    int i, j, k, t; int x, y, n, m;
    scanf ("%d%d", &n, &m);
    for (i = 1; i <= m; ++ i)
    {
        scanf ("%d%d", &x, &y);
        f[x][y][0] = 1;
        g[x][y] = 1;
    }
    for (t = 1; t <= 33; ++ t) for (k = 1; k <= n; ++ k) for (i = 1; i <= n; ++ i) for (j = 1; j <= n; ++ j)
            if (f[i][k][t - 1] && f[k][j][t - 1])
                  f[i][j][t] = 1, g[i][j] = 1;
    for (k = 1; k <= n; ++ k) for (i = 1; i <= n; ++ i) for (j = 1; j <= n; ++ j)
            g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    cout << g[1][n];
    return 0;
}

int youngore = thestars();

signed main() {;}

仓鼠找妹子

click

我真希望随手就能切了，但是时间显然不允许

我们容易发现，如果相交，记\(x=lca(a,b)，y=lca(c,d)\) ，则必有x在c ~ d路径上或y在a ~ b路径上

证明?：画一个图发现举不出反例就是对的

qbxt某dalao的原话：

•证明一下：易知两点的lca在其路径上。如果路径相交，那么x要么在相交的路径上，要么不在。我们不妨记相交的那段为e~f

•如果不在，由对称性，不妨设x靠近a，那么有a到x深度递减，b到e、e到f、f到x深度递减；同样，肯定有c到f、d到e深度递减，由此可知，y必定为f，由此得证（以上的e、f和c、d的相对位置是由对称性直接设的，各位不妨画图理解一下）

•如果在的话就更好证了

还剩下一件事情，那么如何查看一个点是否在一条路径上呢？

给出一个性质：即须满足该点到路径两端点的距离和等于两端点的距离，距离用lca和深度就可以了

设\(lca(u,v)=x\)，则\(u,v\)间距则为\(dep[u]+dep[v]-2*dep[x]\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e5+66;

int head[N << 1], to[N << 1], nex[N << 1], cnt;

inline void add(int x, int y)
{
    to[++ cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt;
}

int S = 20;
int dep[N << 1], f[N << 1][30];

inline void dfs(int x)
{
    int i, y;
    for (i = 1; i <= S; ++ i)
    {
        if (f[x][i - 1])
            f[x][i] = f[f[x][i - 1]][i - 1];
        else break;
    }
    for (i = head[x]; i; i = nex[i])
    {
        y = to[i];
        if (y != f[x][0])
        {
            f[y][0] = x;
            dep[y] = dep[x] + 1;
            dfs(y);
        }
    }
}

inline int LCA(int x, int y)
{
    int i;
    if (dep[x] < dep[y]) swap(x, y);
    int delta = dep[x] - dep[y];
    for (i = 0; i <= S; ++ i)
        if ((1 << i) & delta)
            x = f[x][i];
    if (x == y) return x;
    for (i = S; i >= 0; -- i)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

inline int dis(int x, int y) {return dep[x] + dep[y] - 2 * dep[LCA(x, y)];}

inline int thestars()
{
    int i, n, m, x, y;
    int a, b, c, d;
    scanf ("%d%d", &n, &m);
    for (i = 1; i < n; ++ i)
    {
        scanf ("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    dfs(1); 
    for (i = 1; i <= m; ++ i)
    {
        scanf ("%d%d%d%d", &a, &b, &c, &d);
        x = LCA(a, b), y = LCA(c, d);
        if (dis(a, y) + dis(y, b) == dis(a, b) 
            || dis(c, x) + dis(x, d) == dis(c, d))
            puts("Y");
        else puts("N");
    }
    return 0;
}

int youngore = thestars();

signed main() {;}

货车运输

click

不会，留坑待填

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<cstdio>  
#include<algorithm>  
#include<cstring>  
#include<iostream>  
#define MAXN 10005 
#define INF 999999999
using namespace std; 
struct Edge1{  
    int x,y,dis;
}edge1[50005]; //题目所给的图 
struct Edge2{
    int to,next,w;
}edge2[100005]; //最大生成树的图 
int cnt,n,m,head[MAXN],deep[MAXN],f[MAXN],fa[MAXN][21],w[MAXN][21];
//f数组表示并查集中的父节点，fa数组表示树上的父节点，w数组表示最大载重 
bool vis[MAXN]; 

void addedge(int from, int to, int w)
{ //前向星存图 
    edge2[++cnt].next=head[from];
    edge2[cnt].to=to;
    edge2[cnt].w=w;
    head[from]=cnt;
    return ;
}

bool CMP(Edge1 x, Edge1 y){
    return x.dis>y.dis; //将边权从大到小排序 
}

int find(int x){  //并查集寻找父节点 
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}

void kruskal(){
    sort(edge1+1, edge1+m+1, CMP); 
    for(int i=1; i<=n; i++)
        f[i]=i;  //并查集初始化 
    for(int i=1; i<=m; i++)
        if(find(edge1[i].x)!=find(edge1[i].y)){
            f[find(edge1[i].x)]=find(edge1[i].y);
            addedge(edge1[i].x, edge1[i].y, edge1[i].dis);
            addedge(edge1[i].y, edge1[i].x, edge1[i].dis);  //无向图，双向加边 
        }
    return ;
}

void dfs(int node){
    vis[node]=true;
    for(int i=head[node]; i; i=edge2[i].next){ //前向星遍历 
        int to=edge2[i].to;
        if(vis[to]) continue;
        deep[to]=deep[node]+1; //计算深度 
        fa[to][0]=node; //储存父节点 
        w[to][0]=edge2[i].w; //储存到父节点的权值 
        dfs(to);
    }
    return ;
}

int lca(int x, int y){
    if(find(x)!=find(y)) return -1; //不连通，输出-1 
    int ans=INF;
    if(deep[x]>deep[y]) swap(x,y); //保证y节点更深 
    //将y节点上提到于x节点相同深度 
    for(int i=20; i>=0; i--)
        if(deep[fa[y][i]]>=deep[x]){
            ans=min(ans, w[y][i]);  //更新最大载重（最小边权） 
            y=fa[y][i]; //修改y位置 
        }
    if(x==y) return ans; //如果位置已经相等，直接返回答案 
    //寻找公共祖先 
    for(int i=20; i>=0; i--)
        if(fa[x][i]!=fa[y][i]){
            ans=min(ans, min(w[x][i], w[y][i])); //更新最大载重（最小边权）
            x=fa[x][i]; 
            y=fa[y][i]; //修改x,y位置 
        }
    ans=min(ans, min(w[x][0], w[y][0]));
    //更新此时x,y到公共祖先最大载重，fa[x][0], fa[y][0]即为公共祖先 
    return ans;
}
int main(){
    int x,y,z,q;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++){
        scanf("%d%d%d",&x,&y,&z);
        edge1[i].x=x;
        edge1[i].y=y;
        edge1[i].dis=z;
    } //储存题目所给图 
    kruskal();
    for(int i=1; i<=n; i++)
        if(!vis[i]){ //dfs收集信息 
            deep[i]=1; 
            dfs(i);
            fa[i][0]=i;
            w[i][0]=INF;
        }
    //LCA初始化 
    for(int i=1; i<=20; i++)
        for(int j=1; j<=n; j++){
            fa[j][i]=fa[fa[j][i-1]][i-1]; 
            w[j][i]=min(w[j][i-1], w[fa[j][i-1]][i-1]);
        }
    scanf("%d",&q);
    for(int i=1; i<=q; i++){
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y)); //回答询问 
    }
    return 0;
}

The merchant

click

这题是真的好啊，我要是能把这道题写出来，那基本倍增就没问题了

\(Description\)

n个城市构成一棵树，每个城市都有一种商品有一个固定的价格，一个商人要从一个城市到另一个城市，他会在路途中选取一个城市购买这种商品然后在之后的某个城市卖掉以赚取差价，问最大差价

\(Input\)

第一行一整数n表示城市个数

之后n个整数val[i]表示第i个城市该种商品的价格，之后n-1行每行两个整数u和v表示u城市和v城市有路径，然后输入一整数q表示查询数，每次查询输入两个整数u和v表示商人从u到v路途中可以赚取的最大差价\((1<=n,val[i],q<=50000)\)

\(Output\)

对于每组查询输出一个答案

发现商人要走的路径大体为\(x->LCA->y\)，具体来说，不过三种：

  • 1.在x->LCA途中完成买卖

  • 2.在LCA->y途中完成买卖

  • 3.在x->LCA买，在LCA->y卖

dalao说一眼可以看出来是树上倍增

显然，我们需要维护多个倍增数组

\(Max[i][j]\)：i到i的\(2^j\)之间的最大值

\(Min[i][j]\)：i到i的\(2^j\)之间的最小值

\(Up[i][j]\)：i到i的\(2^j\)父亲之间的差值最大

\(Down[i][j]\)：从i的\(2^j\)到i之间的最大差值

并且显然，我们所要得到的答案，只会来自于两个地方（假如是上升的）：

  • 1.前一段与后一段的最大差值 取一个最大值
  • 2.后一段的最大值 减去 前一段的最小值

对于第二三种情况，类比第一种就可以了

预处理:

两条路径：

计算答案：

困惑：为什么对于第三种情况，也要是往上跳？

还有别的几道好题没找到链接

宝物

贪心可得90分，每个类，取(a+b+c)均值最大的

值得注意的是：对于\(cnt_i = 0\)的类，应当在搜索中直接跳过，否则可能导致T

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
template <typename T>
inline void _read(T& x){
    char ch=getchar();bool sign=true;
    while(!isdigit(ch)){if(ch=='-')sign=false;ch=getchar();}
    for(x=0;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+ch-'0';
    if(!sign)x=-x;
}
int n,k,K;
int t[55],a[55],b[55],c[55];
int id[55][55];
int cnt[55];
int Type[55];

ll ans=0;//记得用long long 否则拿不到100分 

/*void dfs(int num,int A,int B,int C){
    //当前讨论第num个非空类选择哪一个物品（因为选一个一定比不选优） 
    if(num>K){
        ans=max(ans, 1LL*A*B*C);
        return;
    }
    int type=Type[num];//第num个非空类为Type[num] 
    for(int i=1;i<=cnt[type];i++){//依次尝试每一个物品 
        int v=id[type][i];
        dfs(num+1,A+a[v],B+b[v],C+c[v]);
    }
}*/
void dfs(int num,int A,int B,int C){
    //当前讨论第num个类选择哪一个物品（因为选一个一定比不选优） 
    if(num>K){
        ans=max(ans, 1LL*A*B*C);
        return;
    }
    if(cnt[num]==0)dfs(num+1,A,B,C);
    int type=num;//Type[num];//第num个非空类为Type[num] 
    for(int i=1;i<=cnt[type];i++){//依次尝试每一个物品 
        int v=id[type][i];
        dfs(num+1,A+a[v],B+b[v],C+c[v]);
    }
} 
int main(){
    int i,j,type;
    cin>>n>>k;
    
    for(i=1;i<=n;i++){
        _read(type);_read(a[i]);_read(b[i]);_read(c[i]);
        cnt[type]++;  //type类的物品数+1 
        id[type][cnt[type]]=i;  //type类的第cnt[type]个物品编号为i 
    }
    
    //统计所有非空类，K表示非空种类数量，非空的种类存入Type数组 
    for(i=1;i<=k;i++){
        if(cnt[i]==0)continue;
        K++;
        Type[K]=i;
    }
    
    dfs(1,99,99,99);
    
    printf("%lld\n",ans);
}

赛车

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
template <typename T>
inline void _read(T& x){
    char ch=getchar();bool sign=true;
    while(!isdigit(ch)){if(ch=='-')sign=false;ch=getchar();}
    for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    if(!sign)x=-x;
}
int T;
struct node{
    int p,a;
    bool mark;
    node(){}
    node(int P,int A){
        p=P;a=A;mark=false;
    }
};
node car[50005];
bool cmp(node A,node B){
    if(A.a==B.a)return A.p>B.p;
    else return A.a<B.a;
}
int q[50005];
double meet[50005];
int rear;
double solve(int i,int j){
    //if(car[i].p==car[j].p)return 0.0;
    //if((car[i].a<car[j].a&&car[j].p>car[i].p)||(car[i].a>car[j].a&&car[j].p<car[i].p))return -1.0;
    double a1=car[i].a,a2=car[j].a,p1=car[i].p,p2=car[j].p;
    return sqrt(2.0*(p2-p1)/(a1-a2));
}
int main(){
    //freopen("car.in","r",stdin);
    //freopen("car.out","w",stdout);
    T=1;
    int i,j,k,n;
    while(T--){
        memset(car,0,sizeof(car));
        _read(n);
        int ans=0;
        for(i=1;i<=n;i++){
            _read(car[i].p);
            _read(car[i].a);
        }
        sort(car+1,car+1+n,cmp);
        int id=1;
        for(i=2;i<=n;i++){
            if(car[i-1].a==car[i].a&&car[i-1].p==car[i].p){
            //处理p，a都相同的车，mark为true表示存在另一个与他参数相同的车 
                car[i-1].mark=true;
                car[i].mark=true;
            }
        }
        int tot=1;
        for(i=2;i<=n;i++){
            if(car[i].a!=car[i-1].a)car[++tot]=car[i]; 
            //相同加速度的车我们只留一个p最大的 
        }
        //tot=保留的车的数量 
        rear=1;
        q[rear]=1; //把第一个车加进栈 
        for(i=2;i<=tot;i++){ //依次讨论每一辆车 
            while(rear>0&&car[i].p>=car[q[rear]].p)rear--; 
            //如果栈顶车p比当前车小，那么栈顶车可以扔掉(因为它p、a都比当前车小) 
            while(rear>=2){ //栈里还有大于两个车 
                //meet[i]存储q[i]和q[i+1]两辆车相交的时间点 
                if(solve(i,q[rear])<meet[rear-1]+1e-5)rear--; 
                //如果栈顶两车的相交点 不小于 当前车和栈顶车的相交点 栈顶可以扔掉 
                else break;
            }
            q[++rear]=i; //当前车入栈 
            if(rear>1)meet[rear-1]=solve(q[rear-1],q[rear]); //存储对应meet值 
        }
        //q里面就是所有的领跑者 
        for(i=1;i<=rear;i++)if(car[q[i]].mark==false)ans++;
        printf("%d\n",ans);
    }
}