AtCoder Grand Contest 021

AGC难度上天，希望自己可以将题目陆陆续续的都给做出来。
这里的题目质量奇高，一定要好好刷起来，这是第三篇
只要是我做出来的题目，都会认真的写题解的~~

A - Digit Sum 2

对于这种处理数位上的题目，我总是不会做，哎！！！
题目：
给定一个长度为16的数字串，它表示一个大小为10^16大小的数字N，让我们找到1~N中，每位数字和最大的数字。

解决：
尝试给每一位降1，然后他后面的所有数位上的数字都可以变成9，这是最贪心的考虑。
需要注意的一点是，当前数位为0的时候，可以直接跳过，因为，如果当前的0降1需要向前借位，等价于0的前面那数降1

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s; cin >> s;int sum = 0;for (int i = 0; i < s.size(); i ++ ) sum += s[i] - '0';for (int i = 0; i < s.size(); i ++ ){
    if (s[i] == '0') continue;int val = s[i] - '0' - 1;for (int j = 0; j < i - 1; j ++ )val += s[i] - '0';val += (s.size() - i - 1) * 9;sum = max(sum, val);}cout << sum << "\n";return 0;
}

B-Holes

凸包问题，先将修改的别人的代码放在这里，挖一个坑，等能解决了再来解决

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits.h>
#include <sstream>
#include <cctype>
#include <numeric>
#include <bitset>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inlin")using namespace std;#define ios ios::sync_with_stdio(false) , cin.tie(0),cout.tie(0)
#define rep(i, n) for (int i = 0; i < n; ++ i)
#define x first
#define y secondtypedef long long ll;
typedef unsigned long long ULL;
typedef pair<int, int> PII;const int N = 100010, INF = 0x3f3f3f3f, mod = 1e9 + 7, base = 131;
const double eps = 1e-6, PI = acos(-1);struct P {
    ll x, y;int i;inline P() {
    }inline P(ll x, ll y, int i) : x(x), y(y), i(i) {
    }inline P &operator += (P o) {
     return x += o.x, y += o.y, *this; }inline P &operator -= (P o) {
     return x -= o.x, y -= o.y, *this; }inline friend P operator + (P a, P b) {
     return a += b; }inline friend P operator - (P a, P b) {
     return a -= b; }inline friend bool operator < (P a, P b) {
     return a.x == b.x ? a.y < b.y : a.x < b.x; }inline friend ll operator * (P a, P b) {
     return a.x * b.x + a.y * b.y; }inline friend ll operator % (P a, P b) {
     return a.x * b.y - a.y * b.x; }inline friend double operator ^ (P a, P b) {
     return a * b / a.l() / b.l(); }inline double l() {
     return sqrt(*this * *this); }
};int n;inline vector<P> convex_hull(vector<P> a) {
    sort(a.begin(), a.end());vector<P> p;for (int i = 0; i < n; i++) {
    while (p.size() > 1u &&(p.back() - p[p.size()-2]) % (a[i] - p[p.size()-2]) <= 0)p.pop_back();p.push_back(a[i]);}ll m = p.size();for (int i = n - 2; ~i; i--) {
    while (p.size() > m &&(p.back() - p[p.size()-2]) % (a[i] - p[p.size()-2]) <= 0)p.pop_back();p.push_back(a[i]);}p.pop_back();return p;
}inline double calc(P x, P y, P z) {
    return (PI - acos((x - y) ^ (z - y))) / (2 * PI);
}int main() {
    cin >> n;vector<P> a;for (int i = 0, x, y; i < n; i++) cin >> x >> y, a.push_back(P(x, y, i));a = convex_hull(a);vector<double> ans(n);int m = a.size();if (m == 2) for (P o : a) ans[o.i] = 0.5;else for (int i = 0; i < m; i++)ans[a[(i+1)%m].i] = calc(a[i], a[(i+1)%m], a[(i+2)%m]);for (int i = 0; i < n; i++) printf("%.20Lf\n", ans[i]);return 0;
}