acm write up

Quoit Design.cpp

#include <bits/stdc++.h>

using namespace std;

// Quoit Design
//
// 寻找两点之间最短的距离
// 这题标准的算法我不懂
// 但是由于数据很大，不需要搜索全部的数据
// 只需要排序之后的前N个即可完成AC要求
// PS 最好了解一下标准的解法

inline double distance(pair<double, double>& a, pair<double, double>& b) {
    auto dx = a.first - b.first;
    auto dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy);
}

int main() {
    int n;
    while (cin >> n, n) {
        vector<pair<double, double>> data;
        while (n--) {
            double x, y;
            // cin >> x >> y;
            scanf("%lf %lf", &x, &y);
            data.push_back(make_pair(x, y));
        }

        sort(data.begin(), data.end(), [](const pair<double, double>& a, const pair<double, double>& b) {
            // if (a.first - b.first < 1e-6) return a.second < b.second;
            // return a.first < b.first;
            return a.first + a.second < b.first + b.second;
        });

        //二重循环，最寻最短的线段
        double radius = 999999;
        for (int i = 0; i < data.size(); i++) {
            //搜索前两个就可以过，感觉数据有点水水
            for (int j = i + 1; j < min(data.size(), size_t(i + 2)); j++) {  //暴力搜索前N个即可AC
                auto dis = distance(data[i], data[j]);
                if (dis < radius) {
                    radius = dis;
                }
            }
        }
        printf("%.2lf\n", radius / 2);
    }

    return 0;
}

Tian Ji -- The Horse Racing.cpp

#include <bits/stdc++.h>

using namespace std;

// 田忌赛马
// 已知敌方马匹的好坏和出场顺序如何调整自己马匹的出场顺序?
// 如何进行贪心求最优解？

int main() {
    int n;
    while (cin >> n, n) {
        vector<int> tian;
        vector<int> king;
        int speed;
        for (int i = 0; i < n; i++) {
            cin >> speed;
            tian.push_back(speed);
        }
        for (int i = 0; i < n; i++) {
            cin >> speed;
            king.push_back(speed);
        }
        sort(king.rbegin(), king.rend());
        sort(tian.rbegin(), tian.rend());

        pair<int, int> pT = make_pair(0, n - 1), pK = make_pair(0, n - 1);
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (tian[pT.first] > king[pK.first]) {  //田忌的最快的🐎比King最快的快，赢一场
                result++;
                pT.first++;
                pK.first++;
            } else if (tian[pT.first] < king[pK.first]) {  //田忌最快的🐎比king最快的慢，用最差的🐎输一场
                result--;
                pT.second--;
                pK.first++;
            } else {
                //两者的🐎一样快，是否平局
                if (tian[pT.second] > king[pK.second]) {  //田忌最慢的🐎比king最慢的快，赢一场
                    result++;
                    pT.second--;
                    pK.second--;
                } else if (tian[pT.second] <= king[pK.second]) {  // 不论结果如何，用田忌最慢的🐎换King的一匹好🐎
                    result -= tian[pT.second] < king[pK.first];
                    pT.second--;
                    pK.first++;
                }
            }
        }
        cout << result * 200 << endl;
    }
    return 0;
}