杭电acm多校 1009

题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1009&cid=879

这是我的代码：

#include <iostream>
#include <cstdio> 　　　　 //定义输入／输出函数
#include <stack>　　　　　 //STL 堆栈容器
#include <map>　　　　　　 //STL 映射容器
#include<set>
#include <vector>　　　　　//STL 动态数组容器
#include <string>　　　　　//字符串类
#include <iterator>        //STL迭代器
#include <cstdlib> 　　　　//定义杂项函数及内存分配函数
#include <cstring> 　　　　//字符串处理ed
#include<algorithm>
#include<queue>
#include<cmath>
#include<fstream>
#include<ctime>
using namespace std;
#define ll long long 
#define FOR(ITER,BEGIN,END)  for(int  ITER=BEGIN;ITER<END;ITER++)
#define PER(ITER,TIMES) FOR(ITER,0,TIMES)
#define TIME(TIME_NUMBER) PER(_PETER_MRSCO_ITER_,TIME_NUMBER)
#define close_stdin ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define out_put(l,r,aaaa) {for (int i=l;i<=r;i++){cout<<aaaa[i]<<" ";}cout<<"\n";}
const int maxn = 50010;
const long double eps = 1e-20;
struct robot {
    long double k, b;
    int id, w;
    bool operator<(robot const& ty) {
        if (k == ty.k) { return b > ty.b; }
        return k > ty.k;
    }
    bool  operator ==(robot const ty) {
        return k == ty.k;
    }
    long double operator -(robot const& ty) {
        return (b - ty.b) / (ty.k - k);
    }
};
int n;
robot a[maxn];
int  sta[maxn],top;
ifstream infile("D:\leading-robots.in", ios::in);
void solve() {
    //cin >> n;
    infile >> n;
    map<pair<int, int>, int > mp;
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        int k, b;
        //cin >> k >> b;
        infile >> k >> b;
        pair<int, int> now = { k,b };
        if (!mp[now]) {
            mp[now] = ++cnt;
            a[cnt].k = k;a[cnt].b = b;
            a[cnt].id = cnt;a[cnt].w = 1;
        }
        else {
            a[mp[now]].w++;
        }
    }
    //cnt = n;
    a[++cnt].k = -1;a[cnt].b = 0;
    a[cnt].id = cnt;a[cnt].w = 1;
    sort(a + 1, a + 1 + cnt);
    top = 2;
    sta[1] = 1;
    for (int i = 2;i <= cnt;i++) {
        if (a[i] == a[i - 1]) { continue; }
        while (top >= 3 && ((a[sta[top - 1]] - a[sta[top - 2]]) - (a[sta[top - 1]] - a[i]) <= eps)) { top--; };
        sta[top++] = i;
    }
    int ans = 0;
    for (int i = 1;i < top;i++) { if (a[sta[i]].w < 2)ans++; }
    cout << ans - 1 << "\n";
    for (int i = 1;i <= cnt;i++) { a[cnt].k = a[cnt].b = a[cnt].id = a[cnt].w = 0; }
}
int main() {
    //  presolve();
    ///close_stdin;
    int t;
    //cin >> t;
    infile >> t;
    while (t--) {
        solve();
    }
}

这是zpgg的代码：

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<stdio.h>
#include<stack>
#include<fstream>
using namespace std;
#define close_stdin ios::sync_with_stdio(false)

const int maxn = 50003;
//a加速度，p初始位置 
map<int, set<int> > repeat;  //a-p，重复的点 
map<int, set<int> >indata;    //a-p，输入数据 
map<int, int>robots;    //a-p,每个a对应的p 
set<int> ai;    //所有a 
vector<int> st;    //单调栈 （stack），存a 
ifstream infile("C:\\Users\\86139\\Desktop\\robots.txt", ios::in);


//单调栈插入加速度为a的点 
int insert(int a) {
    //初始位置太靠后则直接结束，因为加速度小且位置靠后则不可能变成leader，反之可能 
    if (robots[a] <= robots[*st.rbegin()]) {
        return 0;
    }
    while (1) {
        //栈中只有一个元素时a入栈结束 
        if (st.size() < 2) { st.push_back(a); return 0; }
        long long aa, pa, ab, pb, ac, pc;
        aa = st[st.size() - 2];
        pa = robots[aa];
        ab = st[st.size() - 1];
        pb = robots[ab];
        ac = a;
        pc = robots[ac];
        long long left, right;
        left = (pb - pa) * (ab - ac);
        right = (aa - ab) * (pc - pb);
        //判断，某栈里前一个点不被覆盖则将此点入栈，否则前一个点出栈继续循环 
        if (left > right) { st.push_back(a); return 0; }
        else {
            st.pop_back();
        }
    }


}

int solve() {
    int n;
    //cin >> n;
    infile >> n;
    repeat.clear();
    indata.clear();
    robots.clear();
    ai.clear();
    st.clear();

    //输入a，p，存入ai，indata和repeat
    int a, p;
    for (int i = 0; i < n; i++) {
        //cin >> a >> p;
        infile >> a >> p;
        ai.insert(a);
        if (indata[a].find(p) != indata[a].end()) {
            repeat[a].insert(p);
        }
        else {
            indata[a].insert(p);
        }
    }
    //每个a对应的可能成为leader的p只有一个，即最大的一个 
    for (set<int>::iterator i = ai.begin(); i != ai.end(); i++) {
        robots[*i] = *indata[*i].rbegin();
    }

    //起始放入最大a 
    st.push_back(*ai.rbegin());
    //从大到小遍历a，将a插入st 
    for (set<int>::iterator i = ai.end(); 1; i--) {
        if (i == ai.end()) { continue; }
        insert(*i);
        if (i == ai.begin()) { break; }
    }

    int result = 0;
    for (vector<int>::iterator i = st.begin(); i != st.end(); i++) {
        //cout<<result<<endl;
        //判断leader点是否重复，对于st中a，robot对应p是indata中最大的，与repeat中此a对应p的最大值比较即可，不同则不重复，结果加一 
        if (repeat[*i].empty() or *repeat[*i].rbegin() != robots[*i]) { result++; }
    }
    cout << result << endl;
    return 0;
}

int main() {
    int t;
    //cin >> t;
    infile >> t;
    while (t--) { solve(); }
    return 0;
}