黑洞内窥：

给出n和m，然后给出n组a， b，代表 x = b（mod a）

(1≤n≤100,1≤m≤10^18， 0<=b<a<10^5)

如果无解输出："he was definitely lying"

如果有解且超过了m，输出："he was probably lying"

否则输出这个解的大小

思维光年：

中国剩余定理模板题，但是会爆longlong，

所以你需要用大数写，比如：pathon，java 或者用__int128

ACcode： 

#include<stdio.h>
#include<cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
typedef __int128 ll;
using namespace std;
#define MAXN 105
#define INF 0x3f3f3f3f//将近int类型最大数的一半，而且乘2不会爆int
#define MOD 1000000007 // MOD%4 = 3
const double pi = acos(-1.0);
const double eps = 1e-6;

ll b[MAXN], w[MAXN];		//w为除数，b是余数
ll read()                      //__int128不能用普通的scanf和cin读入。。
{
    long long x;
    scanf("%lld", &x);
    return x;
}

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll gcd = exgcd(b, a%b, x, y);
    ll t = x;
    x = y;
    y = t - a/b*y;
    return gcd;
}

ll China(ll B[], ll W[], ll k, ll m) //W为除数，B是余数
{
    ll i, a, b, c, d, x, y, t;
    for(i=1; i<k; ++i)
    {
        a = W[i-1], b = W[i];
        c = B[i] - B[i-1];
        d = exgcd(a, b, x, y);
        if(c%d)
            return -1;
        t = b/d;
        x = (x*(c/d)%t+t)%t;
        B[i] = B[i-1] + W[i-1]*x;
        W[i] = W[i]/d*W[i-1];
    }
    return B[k-1];
}

int main()
{
    ll n, m, ans;
    n = read(), m = read();
    for(int i=0; i<n; ++i)
    {
        w[i] = read();
        b[i] = read();
    }
    ans = China(b, w, n, m);
    if(ans == -1) puts("he was definitely lying");
    else if(ans <= m) cout << (long long)ans << '\n';
    else puts("he was probably lying");
    return 0;
}

G：Road Construction


黑洞内窥：

给出n个居民的坐标点，且n为偶数，要你设计一条道路满足下面三个要求：

1-道路不应穿过城市居民；

2-道路两侧的居民人数相等；

3-居民到道路的最小距离最大化。

求：居民到你计划修建的道路的最小距离

思维光年：


我这也不好解释，参考一下这篇CSDN的博客吧！

2019牛客暑期多校训练营（第十场）G    Road Construction 不算几何的思维几何：https://blog.csdn.net/qq_41955236/article/details/99697251


ACcode： 


#include<stdio.h>
#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
#define MAXN 505
#define INF 0x3f3f3f3f//将近int类型最大数的一半，而且乘2不会爆int
#define MOD 1000000007 // MOD%4 = 3
const double pi = acos(-1.0);
const double eps = 1e-6;

struct point
{
    double x, y;
}stu[MAXN];
double a[MAXN], ans = 0;
int n;

void jvli(double k)                ///求两条平行线之间的距离
{
    for(int i=1; i<=n; ++i)
        a[i] = (k*stu[i].x - stu[i].y)/sqrt(k*k+1);
    sort(a+1, a+n+1);
    ans = max(ans, a[n/2+1] - a[n/2]);    //求中间的两条平行线中点的距离中点
}

int main()
{
    cin >> n;
    for(int i=1; i<=n; ++i)
        scanf("%lf %lf", &stu[i].x, &stu[i].y);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
        {
            double k = (stu[j].y - stu[i].y)/(stu[j].x - stu[i].x);
            jvli(k);                //平行    
            jvli(-1.0/k);           //垂直
        }
        printf("%.15f\n", ans/2);
    return 0;
}