网易雷火笔试—三角形朝向题目AC代码

//
// Created by max on 19-9-15.
//
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

struct  Tri
{
    int a;
    int b;
    int c;
    bool isRight = false;
};


void changeOrder(Tri &t)  //调整正反顺序 abc -> cba
{
    int a = t.a;
    int b = t.b;
    int c = t.c;
    t.a = c;
    t.b = b;
    t.c = a;
}

void changeOrder_min(Tri &t)  //调整为以最小开头
{
    int a = t.a;
    int b = t.b;
    int c = t.c;

    int minE;
    if(a < b)
        minE = a;
    else
        minE = b;
    if(c < minE)
        minE = c;

    if(minE == a)
        return;  //不需要调整

    if(minE == b)
    {
        t.a = b;
        t.b = c;
        t.c = a;
        return;
    }

    if(minE == c)
    {
        t.a = c;
        t.b = a;
        t.c = b;
        return;
    }

}


bool isLink ( Tri ti, Tri tj)  //a是目标 b是参考
{
    int cnt=0;
    int ai = ti.a, bi = ti.b, ci = ti.c;
    int aj = tj.a, bj = tj.b, cj = tj.c;

    if(ai == aj || ai == bj || ai == cj)
        cnt++;
    if(bi == aj || bi == bj || bi == cj)
        cnt++;
    if(ci == aj || ci == bj || ci == cj)
        cnt++;

    if(cnt == 2)
        return true;
    else
        return false;
}


bool isOrderRight(Tri ti, Tri tj)  //ti是否与tj一致
{
    int ai = ti.a, bi = ti.b, ci = ti.c;
    int aj = tj.a, bj = tj.b, cj = tj.c;

    bool flag=true;
    if(ai==aj && bi==bj || ai==bj && bi==cj || ai==cj && bi==aj)
        flag = false;
    if(bi==aj && ci==bj || bi==bj && ci==cj || bi==cj && ci==aj)
        flag = false;
    if(ci==aj && ai==bj || ci==bj && ai==cj || ci==cj && ai==aj)
        flag = false;

    return flag;
}

bool isNotFinal(vector<Tri>& v)
{

    for(int i=0; i<v.size(); i++)
    {
        if(v[i].isRight == false)
            return true;
    }

    return false;
}

int main()
{
    int N, M;
    cin  >> N >> M;

    vector<Tri> vec(M);
    for(int i=0; i<M; ++i)
    {
        cin >> vec[i].a >> vec[i].b >> vec[i].c;
    }

    changeOrder_min(vec[0]);
    vec[0].isRight = true;

    while( isNotFinal(vec) )
    {
        for(int i=1; i<M; ++i)
        {
            Tri t = vec[i];
            bool needChange = false;

            for(int j=0; j<i; ++j)  //遍历之前已排序的的三角形
            {
                if(vec[j].isRight == false)
                    continue;

                if( isLink(vec[i], vec[j]))  // i三角形 与之前的j三角形相连 且j是校正的
                {
                    if( isOrderRight(vec[i], vec[j]) ) //i三角形顺序对
                    {
                        changeOrder_min(vec[i]);  //只需调整最小即可
                        vec[i].isRight = true;
                        break;
                    }
                    else
                    {
                        changeOrder(vec[i]);
                        changeOrder_min(vec[i]);
                        vec[i].isRight = true;
                        break;
                    }
                }

            }

        }


        //再遍历一遍 有些没有调整
        for(int i=1; i<M; ++i)
        {
            if(vec[i].isRight == true)
                continue;

            Tri t = vec[i];

            for(int j=i+1; j<M; ++j)  //遍历之前已排序的的三角形
            {
                if(vec[j].isRight == false)
                    continue;

                if( isLink(vec[i], vec[j]))  // i三角形 与之前的j三角形相连 且j是校正的
                {
                    if( isOrderRight(vec[i], vec[j]) ) //i三角形顺序对
                    {
                        changeOrder_min(vec[i]);  //只需调整最小即可
                        vec[i].isRight = true;
                        break;
                    }
                    else
                    {
                        changeOrder(vec[i]);
                        changeOrder_min(vec[i]);
                        vec[i].isRight = true;
                        break;
                    }
                }

            }
        }
    }


    for(int i=0; i<M; ++i)
    {
        cout << vec[i].a << ' ' << vec[i].b << ' ' << vec[i].c << ' ' << endl;
    }

    return 0;
}