Solved:4

Rank:122

补题:8/10

A digits 2

签到 把这个数写n遍

#include
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
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
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 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= 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
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
using namespace std;
const int INF = 0x3f3f3f3f;

map 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
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
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
#include
#include
#include
#include
#include

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 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 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