ABC033-D 三角形の分類

問題へのリンク

C++のソース

#pragma GCC target("avx2")
#pragma GCC optimize ("-O3", "unroll-loops")

#include <iostream>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>

struct PointDef
{
    int X;
    int Y;
};

int DeriveKyoriJijyou(PointDef p1, PointDef p2);
int GetMax(int p1, int p2);

std::vector<std::string> GetInputValues();

std::string InputPattern = "InputX";

std::vector<std::string> GetInputValues()
{
    std::vector<std::string> InputValuesVect;

    if (InputPattern == "Input1") {
        InputValuesVect.push_back("5");
        InputValuesVect.push_back("1 3");
        InputValuesVect.push_back("2 2");
        InputValuesVect.push_back("3 2");
        InputValuesVect.push_back("4 1");
        InputValuesVect.push_back("4 3");
        //1 2 7
    }
    else if (InputPattern == "Input2") {
        InputValuesVect.push_back("9");
        InputValuesVect.push_back("2 0");
        InputValuesVect.push_back("1 1");
        InputValuesVect.push_back("3 1");
        InputValuesVect.push_back("1 2");
        InputValuesVect.push_back("5 2");
        InputValuesVect.push_back("0 3");
        InputValuesVect.push_back("4 3");
        InputValuesVect.push_back("2 4");
        InputValuesVect.push_back("4 4");
        //27 14 43
    }
    else { //実際の入力
        while (true) {
            std::string wkStr;
            std::getline(std::cin,wkStr);
            if(std::cin.eof()) break;
            InputValuesVect.push_back(wkStr.c_str());
        }
    }

    return InputValuesVect;
}

int main()
{
    std::vector<std::string> InputVect = GetInputValues();

    PointDef PointArr[2000];
    int UB=-1;

    for(int I=1;I<=(int)InputVect.size()-1;I++){
        int X,Y;

        int SpaceInd = InputVect.at(I).find_first_of(" ");

        std::istringstream iss1(InputVect.at(I).substr(0,SpaceInd));
        iss1 >> X;

        std::istringstream iss2(InputVect.at(I).substr(SpaceInd+1));
        iss2 >> Y;

        UB++;
        PointArr[I-1].X=X;
        PointArr[I-1].Y=Y;
    }

    int EikakuCnt=0,TyokkakuCnt=0,DonkakuCnt = 0;

    for (int I = 0; I <= UB; I++) {
        for (int J = I + 1; J <= UB; J++) {
            for (int K = J + 1; K <= UB; K++) {
                int AB2 = DeriveKyoriJijyou(PointArr[I], PointArr[J]);
                int BC2 = DeriveKyoriJijyou(PointArr[J], PointArr[K]);
                int AC2 = DeriveKyoriJijyou(PointArr[I], PointArr[K]);

                //最大の辺の長さ
                int MaxVal = GetMax(AB2, BC2);
                MaxVal = GetMax(MaxVal, AC2);

                if (MaxVal < AB2 + BC2 + AC2 - MaxVal) EikakuCnt++;
                else if (MaxVal == AB2 + BC2 + AC2 - MaxVal) TyokkakuCnt++;
                else DonkakuCnt++;
            }
        }
    }
    printf("%d %d %d\n",EikakuCnt, TyokkakuCnt, DonkakuCnt);
}

// 2点間の距離の2乗を求める
int DeriveKyoriJijyou(PointDef p1, PointDef p2)
{
    int wk1 = (p1.X - p2.X) * (p1.X - p2.X);
    int wk2 = (p1.Y - p2.Y) * (p1.Y - p2.Y);
    return wk1 + wk2;
}

int GetMax(int p1,int p2)
{
    if(p1<p2) return p2;
    return p1;
}

解説

ナイーブ解を、SIMDで高速化してます。