省选测试 9

T1

​ 咕咕咕咕咕.....

T2

​ 给出一些山顶的坐标\((x_i,y_i)\), 每在一个山顶, 你将会找到当前能够看到的最高的山顶(一个山顶\(P\)能看到另一个山顶\(Q\)当且仅当它们的连线\(P,Q\)只与\(P,Q\)相交).

​ 爬到最高的山顶后你会停下来, 要计算对于每个山顶, 如果从这里开始爬, 会爬过几个山顶.(重复经过算多次). \(y\)坐标相同的情况下选\(x\)比较大的作为最高山顶.

​ \(n <= 5e5, 0 <= x_i, y_i<= 1e6\)

​

​ 单调栈.

​ 首先我们需要知道在一个山顶可以看到最高的山顶是哪里, 直接单调栈就好了.

​ 设\(to[i]\)为\(i\)这个点为可以看到的最高的点. 我们在往\(to[i]\)走的时候, 可能会经过\(j\)点, \(to[j].y > to[i].y\), 这时候我们需要改变要去的点, 变为\(to[j]\), 也就是说我们需要在\(j\)的答案上再加上一些\(i\)到\(j\)经过的点才能得到\(i\)的答案.

​ 很容易发现这样的关系可以构成一颗树, 我们如果可以找到每个点应该从那些点的答案更新过来, 那么我们就可以建出一颗树, 在树上求出每个点到根的距离就是最终答案了.

​ 设\(pre[i]\)是\(i\)前面第一个\(to[pre[i]].y > to[i].y\)的位置, \(nxt[i]\)是\(i\)后面第一个\(to[nxt[i]].y > to[i].y\)的位置. 如果\(to[i] > i\), 那么我们要走到\(nxt[i]\), 如果\(to[i] < i\), 那么我们要走到\(pre[i]\).

​ 找出每个点的\(pre, nxt\)也用单调栈就可以了.

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 5e5 + 5;
const double eps = 1e-9;
int n, top;
int to[N], pre[N], nxt[N], sta[N];
struct point {
    double x, y;
    point() {}
    point(double X, double Y) { x = X; y = Y; }
} a[N];

point operator - (const point &a, const point &b) { return point(a.x - b.x, a.y - b.y); }

double Cro(point a, point b) { return a.x * b.y - a.y * b.x; }

int dcmp(double x) {
    if(fabs(x) < eps) return 0;
    return x > 0 ? 1 : -1; 
}

void get_to() {
    sta[++ top] = 1; sta[++ top] = 2;
    pre[1] = 1; pre[2] = 1;
    for(int i = 3;i <= n; i++) {
        while(top >= 2 && dcmp(Cro(a[sta[top]] - a[sta[top - 1]], a[i] - a[sta[top - 1]])) > 0) top --;
        sta[++ top] = i; pre[i] = sta[top - 1]; 
    }
    top = 0; sta[++ top] = n; sta[++ top] = n - 1;
    nxt[n] = n; nxt[n - 1] = n;
    for(int i = n - 2;i >= 1; i--) {
        while(top >= 2 && dcmp(Cro(a[sta[top]] - a[sta[top - 1]], a[i] - a[sta[top - 1]])) < 0) top --;
        sta[++ top] = i; nxt[i] = sta[top - 1];
    }
    for(int i = 1;i <= n; i++) {
        // cout << i << " " << pre[i] << " " << nxt[i] << "\n";
        if(a[nxt[i]].y >= a[pre[i]].y) to[i] = nxt[i];
        else to[i] = pre[i];
        // printf("%d : %d\n", i, to[i]);
    }
}

int rt, cnt;
int head[N];
long long ans[N];
struct edge { int to, nxt, val; } e[N << 1];

void add(int x, int y, int z) {
    // cout << x << " " << y << "!!!\n";
    e[++ cnt].nxt = head[x]; head[x] = cnt; e[cnt].to = y; e[cnt].val = z;
}

int cmp(int i, int j) {
    if(a[to[i]].y > a[to[j]].y) return 1;
    else if(a[to[i]].y == a[to[j]].y) return a[to[i]].x > a[to[j]].x;
    return 0;
}

void get_pre_nxt() {
    top = 0;
    for(int i = 1;i <= n; i++) {
        while(top && cmp(i, sta[top])) top --;
        // if(i == 9) cout << top << " " << sta[top] << " " << (a[to[sta[top]]].y < a[to[i]].y) << "++++++++++++\n";
        if(top) pre[i] = sta[top];
        else pre[i] = to[i];
        sta[++ top] = i;
    } 
    top = 0;
    for(int i = n;i >= 1; i--) {
        while(top && cmp(i, sta[top])) top --; // ***
        // if(i == 1) cout << top << " " << sta[top] << "\n";
        if(top) nxt[i] = sta[top];
        else nxt[i] = to[i];
        sta[++ top] = i;
    }
    int Max = 0;
    for(int i = 1;i <= n; i++) 
        if(a[i].y >= Max) Max = a[i].y, rt = i;
    for(int i = 1;i <= n; i++) {
        // cout << i << ":" << pre[i] << " " << nxt[i] << "\n";
        if(i == rt) continue ;
        if(to[i] < i) add(max(to[i], pre[i]), i, i - max(to[i], pre[i])); // ***
        if(to[i] > i) add(min(to[i], nxt[i]), i, min(to[i], nxt[i]) - i); // ***
    }
}

void get_ans(int x) {
    for(int i = head[x]; i ; i = e[i].nxt) {
        int y = e[i].to; 
        // cout << x << " " << y << "\n";
        ans[y] = ans[x] + e[i].val; get_ans(y);
    }
}

int main() {

    freopen("mountain.in","r",stdin); freopen("mountain.out","w",stdout);

    n = read(); 
    for(int i = 1;i <= n; i++) a[i].x = read(), a[i].y = read();
    get_to(); get_pre_nxt(); get_ans(rt);
    for(int i = 1;i <= n; i++) printf("%lld\n", ans[i]);

    fclose(stdin); fclose(stdout);

    return 0;
}
/*
4
0 10
1 5
2 0
3 6

10
0 19
1 6
2 9
3 1
4 18
5 16
6 6
7 7
8 18
9 19
*/

T3

​ 小 K 养了 只鸽子，这 只鸽子可以看成平面直角坐标系内的 n 个固定的整点。

​ 同时，为了看住这些鸽子，小 K 可以在 m 个给定的点上选择其中的若干个点安装监视器。

​ 对于一只鸽子，它被监视当且仅当下面三个条件之一成立：

• 这只鸽子的位置恰好和某个监视器重合。

• 这只鸽子在其中两个位置不同的监视器连接形成的线段上。

• 这只鸽子在三个不共线的监视器所构成的三角形.

​ 现在小 K 要让所有鸽子都被监视，请问他最少需要选择多少个给定的位置设置监视器。

\(2 <= n <= 1e5,3 <= m <= 500\).

​ 凸包.

​ 对于两个监视器\(A,B\), 我们可以连一条从\(A\)到\(B\)的边(注意有方向)当且仅当所有鸽子都在它的左边, 这个用叉积判断就可以了.

​ 所有监视器都连完边后, 我们用Floyd求最小环就可以得到答案了.

​ 怎么判断所有鸽子都在一条线的左边呢? 我们可以把鸽子的凸包求出来, 只需要判断离这条直线最近的点是否在直线的左边就好了.我们可以在凸包上二分斜率来得到这个点.

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 1e5 + 5, inf = 1e9;
const double eps = 1e-9;
int n, m, topx, tops;
struct point { 
    double x, y; 
    point() {}
    point(double X, double Y) { x = X; y = Y; }
    friend int operator < (const point &a, const point &b) {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    }
} a[N], b[N], stax[N], stas[N];

point operator - (const point &a, const point &b) { return point(a.x - b.x, a.y - b.y); }

double Cro(point a, point b) { return a.x * b.y - a.y * b.x; }

int dcmp(double x) {
    if(fabs(x) < eps) return 0;
    return x > 0 ? 1 : -1;
}

void ConvexHall() {
    sort(a + 1, a + n + 1);
    stax[++ topx] = a[1]; stax[++ topx] = a[2];
    for(int i = 3;i <= n; i++) {
        while(topx >= 2 && dcmp(Cro(stax[topx] - stax[topx - 1], a[i] - stax[topx - 1])) <= 0) topx --;
        stax[++ topx] = a[i];
    }
    stas[++ tops] = a[n]; stas[++ tops] = a[n - 1];
    for(int i = n - 2;i >= 1; i--) {
        while(tops >= 2 && dcmp(Cro(stas[tops] - stas[tops - 1], a[i] - stas[tops - 1])) <= 0) tops --;
        stas[++ tops] = a[i];
    }
}

double xl(point a, point b) {
    return (a.y - b.y) / (a.x - b.x);
}

int judge(int i, int j) {
    double k = xl(b[i], b[j]);
    // cout << i << " " << j << " " << k << "\n";
    int l = 2, r = tops - 1, mid;
    point ans1 = a[1], ans2 = a[n];
    while(l <= r) {
        mid = (l + r) >> 1;
        // cout << l << " " << r << "\n";
        double z1 = xl(stas[mid - 1], stas[mid]), z2 = xl(stas[mid], stas[mid + 1]);
        int t1 = dcmp(k - z1), t2 = dcmp(k - z2);
        if((t1 == 0 && t2 == 0) || (t1 != t2)) { ans1 = stas[mid]; break; } 
        else if(t1 > 0 && t2 > 0) r = mid - 1;
        else l = mid + 1;
    }
    l = 2, r = topx - 1;
    while(l <= r) {
        mid = (l + r) >> 1;
        // cout << l << " " << r << "\n";
        double z1 = xl(stax[mid - 1], stax[mid]), z2 = xl(stax[mid], stax[mid + 1]);
        int t1 = dcmp(k - z1), t2 = dcmp(k - z2);
        if((t1 == 0 && t2 == 0) || (t1 != t2)) { ans2 = stax[mid]; break; } 
        else if(t1 < 0 && t2 < 0) r = mid - 1;
        else l = mid + 1;
    }
    if(dcmp(Cro(ans1 - b[i], b[j] - b[i])) >= 0) {
        if(dcmp(Cro(a[1] - b[i], b[j] - b[i])) >= 0 && dcmp(Cro(a[n] - b[i], b[j] - b[i])) >= 0) return 1;
    }
    else if(dcmp(Cro(ans2 - b[i], b[j] - b[i])) <= 0) {
        if(dcmp(Cro(a[1] - b[i], b[j] - b[i])) <= 0 && dcmp(Cro(a[n] - b[i], b[j] - b[i])) <= 0) return 1;
    }
    else return 0;
}

long long ans;
long long f[505][505], d[505][505];

int main() {

    freopen("lo.in","r",stdin); freopen("lo.out","w",stdout);

    n = read(); m = read();
    for(int i = 1;i <= n; i++) a[i].x = read(), a[i].y = read(); 
    for(int i = 1;i <= m; i++) b[i].x = read(), b[i].y = read();
    ConvexHall();
    // for(int i = 1;i <= tops; i++) cout << stas[i].x << " " << stas[i].y << "!!!\n";
    // for(int i = 1;i <= topx; i++) cout << stax[i].x << " " << stax[i].y << "|||\n"; 

    ans = inf;
    for(int i = 1;i <= m; i++)
        for(int j = 1;j <= m; j++) f[i][j] = d[i][j] = inf;
    sort(b + 1, b + m + 1);
    for(int i = 1;i <= m; i++)
        for(int j = i + 1;j <= m; j++) 
            if(judge(i, j)) f[i][j] = f[j][i] = d[i][j] = d[j][i] = 1;
    
    for(int k = 1;k <= m; k++) {
        for(int i = 1;i <= m; i++) {
            for(int j = 1;j <= m; j++) {
                ans = min(ans, d[i][k] + d[k][j] + f[i][j]);
            }
        }
        for(int i = 1;i <= m; i++) {
            for(int j = 1;j <= m; j++) {
                ans = min(ans, f[i][k] + f[k][j] + f[i][j]);
                // cout << f[i][k] << " " << f[k][j] << " " << f[i][j] << "\n";
                if(f[i][k] + f[k][j] < f[i][j]) f[i][j] = f[i][k] + f[k][j];
            }
        }
    }
    printf("%lld", ans > m ? -1 : ans);


    fclose(stdin); fclose(stdout);

    return 0;
}

/*
4 4
0 0
1 0
0 1
-1 0
0 1
1 0
0 -1
-1 0

2 4
-1 0
1 0
-2 -1
-2 1
2 -1
2 1
*/