2019牛客多校 Round5

Solved:4

Rank:122

补题:8/10

A digits 2

签到把这个数写n遍

#include <bits/stdc++.h>

using namespace std;

int T;

int n;

int main(){

    scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        for(int i=1;i<=n;i++)printf("%d",n);

        puts("");

    }

    return 0;

}

digits 2

B generator 1

题意:求矩阵快速幂幂超级大

题解:10进制模拟矩阵快速幂

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll mod;

struct node {

    ll c[2][2];

};

node mul(node x, node y) {

    node res;

    memset(res.c, 0, sizeof(res.c));

    for(int i = 0; i < 2; i++)

    for(int j = 0; j < 2; j++)

    for(int k = 0; k < 2; k++)

        res.c[i][j] = (res.c[i][j] + x.c[i][k] * y.c[k][j] % mod) % mod;

    return res;

}

node pow_mod(node x, ll y) {

    node res;

    res.c[0][0] = res.c[1][1] = 1LL;

    res.c[0][1] = res.c[1][0] = 0LL;

    while(y) {

        if(y & 1) res = mul(res, x);

        x = mul(x, x);

        y >>= 1;

    }

    return res;

}

char s[1000005];

int ss[1000005];

int main() {

    ll x0, x1, a, b;

    cin>>x0>>x1>>a>>b;

    scanf("%s", s + 1);

    int len = strlen(s + 1);

    for(int i = 1; i <= len; i++) ss[i] = s[i] - '0';

    cin>>mod;

    node A;

    A.c[0][0] = a;

    A.c[0][1] = b;

    A.c[1][0] = 1LL;

    A.c[1][1] = 0LL;

    if(len == 1) {

        if(s[1] == '1') {

            printf("%lld\n", x1);

            return 0;

        }

    }

    ss[len]--;

    for(int i = len; i >= 1; i--) {

        if(ss[i] < 0) {

            ss[i] += 10;

            ss[i - 1]--;

        }

    }

    node now;

    now.c[0][0] = now.c[1][1] = 1LL; now.c[0][1] = now.c[1][0] = 0LL;

    for(int i = 1; i <= len; i++) {

        now = pow_mod(now, 10);

        int t = ss[i];

        node pp = pow_mod(A, 1LL * t);

        now = mul(now, pp);

    }

    ll ans = now.c[0][0] * x1 % mod + now.c[0][1] * x0 % mod;

    ans %= mod;

    printf("%lld\n", ans);

    return 0;

}

generator 1

C generator 2 (BSGS)

只是大概了解了下BSGS的大概思想.. 题是学弟补的 orz (我摸鱼了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1000000;

int T;

ll x0,n,a,b,p;

ll ksm(ll a,ll b){

    ll res = 1;

    for(;b;b>>=1){

        if(b & 1)res = res*a%p;

        a = a * a % p;

    }

    return res;

}

pair<int,int> node[maxn];

int pos[maxn],val[maxn];

int main(){

    scanf("%d",&T);

    while(T--){

        scanf("%lld%lld%lld%lld%lld",&n,&x0,&a,&b,&p);

        int Q;scanf("%d",&Q);

        if(a == 0){

            while(Q--){

                int v;scanf("%d",&v);

                if(v == x0)

                    puts("0");

                else if(v == b) puts("1");

                else puts("-1");

            }

            continue;

        }

        ll now = x0;

        int up = min(n,(ll)maxn);

        for(int i=0;i<up;i++){

            node[i] = {now,i};

            now = (now * a + b) % p;

        }

        sort(node,node+up);

        int  m = 0;

        for(int i=0;i<up;i++){

            val[m] = node[i].first;

            pos[m++] = node[i].second;

            while(i < up - 1 && node[i].first == node[i+1].first)i++;

        }

        int inv_a = ksm(a,p-2);

        int inv_b = (p-b)%p*inv_a%p;

        ll bb = 0, aa = 1;

        for(int i=0;i<maxn;i++){

            aa = aa * inv_a % p;

            bb = (bb*a%p + b) % p;

        }

        int r = p / maxn + 1;

        while(Q--){

            int v;scanf("%d",&v);

            int id = lower_bound(val,val+m,v) - val;

            if(id < m && val[id] == v){

                printf("%d\n",pos[id]);continue;

            }

            if(n < maxn){

                puts("-1");continue;

            }

            bool flag = false;

            for(int i=1;i<=r;i++){

                v = (v-bb+p)%p*aa%p;

                int id = lower_bound(val,val+m,v) - val;

                if(id < m && val[id] == v){

                    int res = pos[id] + i * maxn;

                    if(res >= n)puts("-1");

                    else printf("%d\n",res);

                    flag = true;break;

                }

            }

            if(!flag)puts("-1");

        }

    }

    return 0;

}

generator 2

E independent set 1 (状压DP)

题意:最多26个点一共有1<<26个子集求所有子集最大独立集的和

题解:看题解补的.. 看到26个点以为int根本开不下状压的数组结果可以用char开.. 因为每个状态的值不会超过26.. (原来还可以这样

　　于是对于每一个状态选取他最小的一个点可能有两种状态转移过来选了这个点的贡献和不选这个点

　　为什么是最小的就可以.. 因为当前状态是1个1个点慢慢选出来的去掉这个点是子问题

　　还有为什么在算这个点的时候要把和他相邻的点都扣掉.. 我最开始觉得有的点虽然和他相邻但是不一定在那个状态下这个点产生了贡献所以应该不扣

　　扣掉的点肯定不会对最大独立集产生贡献因为是要放入的点相邻的然后扣掉是不扣的子问题所以没区别了

#include <bits/stdc++.h>

using namespace std;

char dp[1 << 26];

int adj[30];

int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; i++) {

        int u, v;

        scanf("%d%d", &u, &v);

        adj[u] |= (1 << v);

        adj[v] |= (1 << u);

    }

    for(int i = 0; i < n; i++) adj[i] = (~adj[i]), adj[i] ^= (1 << i);

    //puts("??");

    for(int i = 1; i < (1 << n); i++) {

        int t = __builtin_ctz(i);

        dp[i] = max(dp[i - (1 << t)], (char)(dp[i & adj[t]] + 1));

    }

    int ans = 0;

    for(int i = 1; i < (1 << n); i++) ans += dp[i];

    printf("%d\n", ans);

    return 0;

}

independent set 1

F maximum clique 1 (最大独立集)

题意:n个数选一个最大的子集使得子集的元素两两不矛盾矛盾是指两个数的二进制至少有两位不一样

题解:不矛盾的话显然两个数xor起来不是2的幂和0 而且我们发现如果两个数的二进制1的个数奇偶性一样的话是一定不矛盾的

　　于是根据二进制1的个数建二分图我跑的最大独立集 = 最小割

　　输出匹配的话如果在最后一次bfs中 dis为INF 且是二分图中连s点的集合的点那么就是被割掉了

　　 dis不为INF的点如果是连t点的集合中的点也是被割掉了因为这个点是肯定跑不到t点的

　　 map常数真的大.... 学了下出题人std判2的幂

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

map<int, int> mp;

int n, s, t, maxflow, cnt;

struct node {

    int to, nex, val;

}E[1300000];

int head[5005];

int cur[5005];

void addedge(int x, int y, int va) {

    E[++cnt].to = y; E[cnt].nex = head[x]; head[x] = cnt; E[cnt].val = va;

    E[++cnt].to = x; E[cnt].nex = head[y]; head[y] = cnt; E[cnt].val = 0;

}

int dis[5005];

bool inque[5005];

int st[1000005];

bool spfa() {

    for(int i = 1; i <= t; i++) dis[i] = INF, inque[i] = 0, cur[i] = head[i];

    int top = 0;

    dis[s] = 0, inque[s] = 1;

    st[++top] = s;

    while(top) {

        int u = st[top];

        top--;

        inque[u] = 0;

        for(int i = head[u]; i; i = E[i].nex) {

            int v = E[i].to;

            if(E[i].val && dis[v] > dis[u] + 1) {

                dis[v] = dis[u] + 1;

                if(!inque[v]) {

                    inque[v] = 1;

                    st[++top] = v;

                }

            }

        }

    }

    return dis[t] != INF;

}

int vis;

int dfs(int x, int flow) {

    if(x == t) {

        vis = 1;

        maxflow += flow;

        return flow;

    }

    int used = 0;

    int rflow = 0;

    for(int i = cur[x]; i; i = E[i].nex) {

        cur[x] = i;

        int v = E[i].to;

        if(E[i].val && dis[v] == dis[x] + 1) {

            if(rflow = dfs(v, min(flow - used, E[i].val))) {

                used += rflow;

                E[i].val -= rflow;

                E[i ^ 1].val += rflow;

                if(used == flow) break;

            }

        }

    }

    return used;

}

void dinic() {

    maxflow = 0;

    while(spfa()) {

        vis = 1;

        while(vis) {

            vis = 0;

            dfs(s, INF);

        }

    }

}

bool is_power2(int x) {

    return x && (x & (x - 1)) == 0;

}

int a[5005];

int er[5005];

int main() {

    scanf("%d", &n);

    cnt = 1;

    s = n + 1;

    t = s + 1;

    for(int i = 1; i <= n; i++) {

        scanf("%d", &a[i]);

        int tot = 0;

        int tmp = a[i];

        while(tmp) {

            if(tmp & 1) tot++;

            tmp >>= 1;

        }

        if(tot & 1) addedge(s, i, 1), er[i] = 1;

        else addedge(i, t, 1), er[i] = 0;

    }

    for(int i = 1; i <= n; i++) {

        for(int j = i + 1; j <= n; j++) {

            if(is_power2(a[i] ^ a[j])) {

                if(er[i]) addedge(i, j, 1);

                else addedge(j, i, 1);

            }

        }

    }

    dinic();

    int ans = n - maxflow;

    printf("%d\n", ans);

    int cn = 0;

    for(int i = 1; i <= n; i++) {

        if(dis[i] == INF) {

            if(!er[i]) {

                cn++;

                if(cn != ans) printf("%d ", a[i]);

                else {

                    printf("%d\n", a[i]);

                    break;

                }

            }

        } else {

            if(er[i]) {

                cn++;

                if(cn != ans) printf("%d ", a[i]);

                else {

                    printf("%d\n", a[i]);

                    break;

                }

            }

        }

    }

    return 0;

}

maximum clique 1

G subsequence 1 (DP)

题意:给s，t的数字串求s中有多少子序列10进制下大于t

题解:dp i,j,k表示s的第i位匹配到t的第j位 k = 0表示这个子序列小于t的前j位 1表示等于 2表示大于模拟即可

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 998244353;

char s[3005];

char t[3005];

ll dp[3005][3005][3];

int main() {

    int T;

    scanf("%d", &T);

    while(T--) {

        int n, m;

        scanf("%d%d", &n, &m);

        scanf("%s", s + 1);

        scanf("%s", t + 1);

        for(int i = 1; i <= n; i++) {

            int t1 = s[i] - '0';

            for(int j = 0; j <= i; j++) dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = 0;

            //dp[i][0][1] = 1;

            //dp[i][0][1] = 1;

            //dp[i][0][2] = 1;

            for(int j = 1; j <= i; j++) {

                int t2 = t[j] - '0';

                dp[i][j][0] = dp[i - 1][j][0];

                dp[i][j][1] = dp[i - 1][j][1];

                dp[i][j][2] = dp[i - 1][j][2];

                if(j == 1) {

                    if(t1 == 0) continue;

                    if(t1 == t2) dp[i][j][1]++;

                    else if(t1 > t2) dp[i][j][2]++;

                    else dp[i][j][0]++;

                } else if(j == m + 1) {

                    dp[i][j][2] += dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];

                    dp[i][j][1] = 0;

                    dp[i][j][0] = 0;

                } else if(j > m + 1) {

                    dp[i][j][2] += dp[i - 1][j - 1][2];

                }

                else {

                    if(t1 == t2) {

                        dp[i][j][1] += dp[i - 1][j - 1][1];

                        dp[i][j][2] += dp[i - 1][j - 1][2];

                        dp[i][j][0] += dp[i - 1][j - 1][0];

                    } else if(t1 > t2) {

                        dp[i][j][2] += dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];

                        dp[i][j][0] += dp[i - 1][j - 1][0];

                    } else {

                        dp[i][j][0] += dp[i - 1][j - 1][1] + dp[i - 1][j - 1][0];

                        dp[i][j][2] += dp[i - 1][j - 1][2];

                    }

                }

                dp[i][j][0] %= mod;

                dp[i][j][1] %= mod;

                dp[i][j][2] %= mod;

            }

        }

        ll ans = 0;

        /*

        for(int i = 1; i <= n; i++) {

            for(int j = 1; j <= i; j++) {

                printf("%d %d %lld %lld %lld\n", i, j, dp[i][j][0], dp[i][j][1], dp[i][j][2]);

            }

        }*/

        for(int i = m; i <= n; i++) {

            ans = (ans + dp[n][i][2]) % mod;

        }

        printf("%lld\n", ans);

    }

    return 0;

}

subsequence 1

H subsequence 2 (模拟)

题意:给一个串的许多信息每次给两种字母然后给出在只剩下这两种字母的情况下原串的样子输出原串

题解:每种信息更新这一种字母前有多少字母最后组成原串

#include <bits/stdc++.h>

using namespace std;

char s[5];

char t[10005];

int num[15];

int pos[15][10005];

int ans[10005];

int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= 10; i++) pos[i][0] = 0;

    for(int i = 1; i <= n; i++) ans[i] = 0;

    bool f = true;

    for(int i = 1; i <= m * (m - 1) / 2; i++) {

        scanf("%s", s + 1);

        int len2; scanf("%d", &len2);

        getchar();

        if(len2 == 0) continue;

        scanf("%s", t + 1);

        int c1 = s[1] - 'a' + 1;

        int c2 = s[2] - 'a' + 1;

        int cn1 = 0, cn2 = 0;

        if(c1 > c2) swap(c1, c2);

        for(int j = 1; j <= len2; j++) {

            if(t[j] - 'a' + 1 == c1) {

                cn1++;

                pos[c1][cn1] += cn2;

            } else if(t[j] - 'a' + 1 == c2) {

                cn2++;

                pos[c2][cn2] += cn1;

            } else {

                f = false;

                break;

            }

        }

        if(pos[c1][0] == 0) pos[c1][0] = cn1;

        else if(pos[c1][0] != cn1) f = false;

        if(pos[c2][0] == 0) pos[c2][0] = cn2;

        else if(pos[c2][0] != cn2) f = false;

    }

    for(int i = 1; i <= m; i++) {

        for(int j = 1; j <= pos[i][0]; j++) {

            //cout << pos[i][j] << " ";

            if(pos[i][j] + j > n) f = false;

            else {

                if(ans[pos[i][j] + j]) f = false;

                else ans[pos[i][j] + j] = i;

            }

        }

        //puts("");

    }

    //puts("f");

    //cout << f <<endl;

    for(int i = 1; i <= n; i++) if(!ans[i]) f = false;

    if(!f) {

        puts("-1");

    } else {

        for(int i = 1; i <= n; i++) {

            printf("%c", ans[i] - 1 + 'a');

        }

        puts("");

    }

    return 0;

}

subsequence 2

I three points 1 (计算几何)

队友补的 (啥东西写了400行???

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

int gcd(int a, int b){

    return b == 0 ? a : gcd(b, a % b);

}

const double eps = 1e-8;

int cmp(double x) {

    if (fabs(x) < eps) return 0;

    if (x > 0) return 1;

    return -1;

}

const double pi = acos(-1.0);

inline double sqr(double x) {

    return x * x;

}

struct point {

    double x, y;

    point() {}

    point(double a, double b) : x(a), y(b) {}

    void input() {

        scanf("%lf%lf", &x, &y);

    }

    friend point operator + (const point &a, const point &b) {

        return point(a.x + b.x, a.y + b.y);

    }

    friend point operator - (const point &a, const point &b) {

        return point(a.x - b.x, a.y - b.y);

    }

    friend bool operator == (const point &a, const point &b) {

        return cmp(a.x - b.x) == 0 && cmp(a.y - b.y) == 0;

    }

    friend point operator * (const point &a, const double &b) {

        return point(a.x * b, a.y * b);

    }

    friend point operator * (const double &a, const point &b) {

        return point(a * b.x, a * b.y);

    }

    friend point operator / (const point &a, const double &b) {

        return point(a.x / b, a.y / b);

    }

    double norm(){

        return sqrt(sqr(x) + sqr(y));

    }

    friend bool operator < (const point a, const point b){

        if(a.x == b.x) return a.y < b.y;

        if(a.y == b.y) return a.x < b.x;

        return a.x < b.x;

    }

};

double det(const point &a, const point &b) {

    return a.x * b.y - a.y * b.x;

}

double dot(const point &a, const point &b) {

    return a.x * b.x + a.y * b.y;

}

double dist(const point &a, const point &b) {

    return  (a - b).norm();

}

point rotate_point(const point &p, double A){

    double tx = p.x, ty = p.y;

    return point(tx * cos(A) - ty * sin(A), tx * sin(A) + ty * cos(A));

}

struct line {

    point a, b;

    line() {}

    line(point x, point y) : a(x), b(y) {}

};

line point_make_line(const point a, const point b) {

    return line(a, b);

}

double dis_point_segment(const point p, const point s, const point t) {

    if(cmp(dot(p - s, t - s)) < 0) return (p - s).norm();

    if(cmp(dot(p - t, s - t)) < 0) return (p - t).norm();

    return fabs(det(s - p, t - p) / dist(s, t));

}

void PointProjLine(const point p, const point s, const point t, point &cp){

    double r = dot((t - s), (p - s)) / dot(t - s, t - s);

    cp = s + r * (t - s);

}

bool PointOnSegment(point p, point s, point t){

    return cmp(det(p - s, t - s)) == 0 && cmp(dot(p - s, p - t)) <= 0;

}

bool parallel(line a, line b){

    return !cmp(det(a.a - a.b, b.a - b.b));

}

bool line_make_point(line a, line b, point &res){

    if(parallel(a, b)) return false;

    double s1 = det(a.a - b.a, b.b - b.a);

    double s2 = det(a.b - b.a, b.b - b.a);

    res = (s1 * a.b - s2 * a.a) / (s1 - s2);

    return true;

}

line move_d(line a, const double &len){

    point d = a.b - a.a;

    d = d / d.norm();

    d = rotate_point(d, pi / 2);

    return line(a.a + d * len, a.b + d * len);

}

bool SegmentSamePoints(line i, line j){

    return max(i.a.x, i.b.x) >= min(j.a.x, j.b.x) &&

            max(j.a.x, j.b.x) >= min(i.a.x, i.b.x) &&

            max(i.a.y, i.b.y) >= min(j.a.y, j.b.y) &&

            max(j.a.y, j.b.y) >= min(i.a.y, i.b.y) &&

            cmp(det(j.a - i.a, i.b - i.a) * det(j.b - i.a, i.b - i.a)) <= 0 &&

            cmp(det(i.a - j.a, j.b - j.a) * det(i.b - j.a, j.b - j.a)) <= 0;

}

double Sabc(point a, point b, point c){

    return fabs(a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y) / 2.0;

}

struct section{

    double l, r;

    section() {}

    section(double a, double b) {

        l = min(a, b);

        r = max(a, b);

    }

    friend bool operator < (section a, section b){

        if(a.l == b.l) return a.r < b.r;

        return a.l < b.l;

    }

};

bool sjs(section a, section b){

    if(b < a) swap(a, b);

    if(a.l < b.l){

        return (a.r > b.l) || (b.r < a.r);

    }

    else{

        return (a.r < b.r);

    }

}

const int maxn = 1005;

struct polygon {

    int n;

    point a[maxn];

    polygon() {}

    double perimeter() {

        double sum = 0;

        a[n] = a[0];

        for(int i = 0; i < n; i++){

            sum += (a[i + 1] - a[i]).norm();

        }

        return sum;

    }

    double area(){

        double sum = 0;

        a[n] = a[0];

        for(int i = 0; i < n; i++){

            sum += det(a[i + 1], a[i]);

        }

        return sum / 2.0;

    }

    int Point_In(point t){

        int num = 0, i, d1, d2, k;

        a[n] = a[0];

        for(i = 0; i < n; i++){

            if(PointOnSegment(t, a[i], a[i + 1])) return 2;

            k = cmp(det(a[i + 1] - a[i], t - a[i]));

            d1 = cmp(a[i].y - t.y);

            d2 = cmp(a[i + 1].y - t.y);

            if(k > 0 && d1 <= 0 && d2 > 0) num++;

            if(k < 0 && d2 <= 0 && d1 > 0) num--;

        }

        return num != 0;

    }

    int Border_Int_Point_Num();

    int Inside_Int_Point_Num();

};

int polygon::Border_Int_Point_Num(){

    int num = 0;

    a[n] = a[0];

    for(int i = 0; i < n; i++){

        num += gcd(abs(int(a[i + 1].x - a[i].x)), abs(int(a[i + 1].y - a[i].y)));

    }

    return num;

}

int polygon::Inside_Int_Point_Num(){

    return int(area()) + 1 - Border_Int_Point_Num() / 2;

}

struct polygon_convex{

    vector<point> P;

    polygon_convex(int Size = 0){

        P.resize(Size);

    }

};

bool comp_less(const point &a, const point &b){

    return cmp(a.x - b.x) < 0 || cmp(a.x - b.x) == 0 && cmp(a.y - b.y) < 0;

}

polygon_convex convex_hull(vector<point> a){

    polygon_convex res(2 * a.size() + 5);

    sort(a.begin(), a.end(), comp_less);

    a.erase(unique(a.begin(), a.end()), a.end());

    int m = 0;

    for(int i = 0; i < a.size(); ++i){

        while(m > 1 && cmp(det(res.P[m - 1] - res.P[m - 2], a[i] - res.P[m - 2])) <= 0)

            --m;

        res.P[m++] = a[i];

    }

    int k = m;

    for(int i = int(a.size()) - 2; i >= 0; --i){

        while(m > k && cmp(det(res.P[m - 1] - res.P[m - 2], a[i] - res.P[m - 2])) <= 0)

            --m;

        res.P[m++] = a[i];

    }

    res.P.resize(m);

    if(a.size() > 1) res.P.resize(m - 1);

    return res;

}

int T;

double a, b, c;

double w, h;

bool w_h_swap = false;

bool wrong(point r){

    return !(cmp(r.x - 0) >= 0 && cmp(w - r.x) >= 0 && cmp(r.y - 0) >= 0 && cmp(h - r.y) >= 0);

}

// #define __DEBUG

int main(){

    scanf("%d", &T);

    #ifdef __DEBUG

    printf("%d\n", T);

    #endif

    while(T--){

        scanf("%lf%lf%lf%lf%lf", &w, &h, &a, &b, &c);

        #ifdef __DEBUG

            printf("%.0f %.0f %.0f %.0f %.0f ", w, h, a, b, c);

        #endif

        double l[3] = {a, b, c};

        sort(l, l + 3);

        w_h_swap = false;

        point A, B, C;

        double dgr;

        A = point(0, 0);

        C = point(-1, -1);

        if(wrong(C)){

            if(l[0] <= w)

                B = point(l[0], 0);

            else

                B = point(w, sqrt(sqr(l[0]) - sqr(w)));

            if(!wrong(B)){

                dgr = acos( (sqr(l[0]) + sqr(l[1]) - sqr(l[2])) / (2 * l[0] * l[1]) );

                C = rotate_point(B, dgr) / B.norm() * l[1];

                if(wrong(C)){

                    dgr = acos( (sqr(l[0]) + sqr(l[2]) - sqr(l[1])) / (2 * l[0] * l[2]) );

                    C = rotate_point(B, dgr) / B.norm() * l[2];

                }

            }

        }

        if(wrong(C)){

            if(l[1] <= w)

                B = point(l[1], 0);

            else

               B = point(w, sqrt(sqr(l[1]) - sqr(w)));

            if(!wrong(B)){

                dgr = acos( (sqr(l[1]) + sqr(l[0]) - sqr(l[2])) / (2 * l[1] * l[0]) );

                C = rotate_point(B, dgr) / B.norm() * l[0];

                if(wrong(C)){

                    dgr = acos( (sqr(l[1]) + sqr(l[2]) - sqr(l[0])) / (2 * l[1] * l[2]) );

                    C = rotate_point(B, dgr) / B.norm() * l[2];

                }

            }

        }

       if(wrong(C)){

            if(l[2] <= w)

                B = point(l[2], 0);

            else

                B = point(w, sqrt(sqr(l[2]) - sqr(w)));

            if(!wrong(B)){

                dgr = acos( (sqr(l[2]) + sqr(l[0]) - sqr(l[1])) / (2 * l[2] * l[0]) );

                C = rotate_point(B, dgr) / B.norm() * l[0];

                if(wrong(C)){

                    dgr = acos( (sqr(l[2]) + sqr(l[1]) - sqr(l[0])) / (2 * l[2] * l[1]) );

                    C = rotate_point(B, dgr) / B.norm() * l[1];

                }

            }

        }

        if(wrong(C)){

            swap(w, h);

            w_h_swap = true;

        }

        if(wrong(C)){

            if(l[0] <= w)

                B = point(l[0], 0);

            else

                B = point(w, sqrt(sqr(l[0]) - sqr(w)));

            if(!wrong(B)){

                dgr = acos( (sqr(l[0]) + sqr(l[1]) - sqr(l[2])) / (2 * l[0] * l[1]) );

                C = rotate_point(B, dgr) / B.norm() * l[1];

                if(wrong(C)){

                    dgr = acos( (sqr(l[0]) + sqr(l[2]) - sqr(l[1])) / (2 * l[0] * l[2]) );

                    C = rotate_point(B, dgr) / B.norm() * l[2];

                }

            }

        }

        if(wrong(C)){

            if(l[1] <= w)

                B = point(l[1], 0);

            else

               B = point(w, sqrt(sqr(l[1]) - sqr(w)));

            if(!wrong(B)){

                dgr = acos( (sqr(l[1]) + sqr(l[0]) - sqr(l[2])) / (2 * l[1] * l[0]) );

                C = rotate_point(B, dgr) / B.norm() * l[0];

                if(wrong(C)){

                    dgr = acos( (sqr(l[1]) + sqr(l[2]) - sqr(l[0])) / (2 * l[1] * l[2]) );

                    C = rotate_point(B, dgr) / B.norm() * l[2];

                }

            }

        }

       if(wrong(C)){

            if(l[2] <= w)

                B = point(l[2], 0);

            else

                B = point(w, sqrt(sqr(l[2]) - sqr(w)));

            if(!wrong(B)){

                dgr = acos( (sqr(l[2]) + sqr(l[0]) - sqr(l[1])) / (2 * l[2] * l[0]) );

                C = rotate_point(B, dgr) / B.norm() * l[0];

                if(wrong(C)){

                    dgr = acos( (sqr(l[2]) + sqr(l[1]) - sqr(l[0])) / (2 * l[2] * l[1]) );

                    C = rotate_point(B, dgr) / B.norm() * l[1];

                }

            }

        }

        if(w_h_swap){

            swap(A.x, A.y);

            swap(B.x, B.y);

            swap(C.x, C.y);

        }

        point ans[3] = {A, B, C};

        point X, Y, Z;

        bool flag = false;

        for(int i = 0; i < 3; i++){

            for(int j = 0; j < 3; j++){

                if(j == i) continue;

                for(int k = 0; k < 3; k++){

                    if(k == i || k == j) continue;

                    X = ans[i];

                    Y = ans[j];

                    Z = ans[k];

                    if(cmp(dist(X, Y) - a) == 0 &&

                        cmp(dist(X, Z) - b) == 0 &&

                        cmp(dist(Y, Z) - c) == 0){

                        flag = true;

                        break;

                    }

                }

                if(flag) break;

            }

            if(flag) break;

        }

        printf("%.8f %.8f %.8f %.8f %.8f %.8f\n", X.x, X.y, Y.x, Y.y, Z.x, Z.y);

    }

    return 0;

}

three points 1

巴特西

2019牛客多校 Round5

最新文章

热门文章