Code Submission Evaluation System Login

CSES - HIIT Open 2018

HIIT Open 2018

Contest start:2018-05-26 11:00:00
Contest end:2018-05-26 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2018-05-26 15:49:45
2018-05-26 15:46:38
Task:Euclidean Geometry
Sender:Wave of Technology
Submission time:2018-05-26 15:49:45
Status:READY
Result:ACCEPTED

Show test data

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:152:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int ind = 0; ind < C.size(); ind++)
                          ~~~~^~~~~~~~~~
input/code.cpp:173:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < C.size(); i++)
                        ~~^~~~~~~~~~

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> T;
vector<int> C;


bool has1neighbour(int i, int j)
{
    for(int diffi = -1; diffi <= 1; diffi++)
    for(int diffj = -1; diffj <=1; diffj++)
    {
        int newi = i+diffi;
        int newj = j + diffj;
        if(newi < 0 || newi > 101 || newj < 0 || newj > 101)
         continue;
        if(T[newi*102+newj] == 1)
            return true;
    }

    return false;
}


int diffsi[4] = {0,0,1,-1};
int diffsj[4] = {1,-1,0,0};


void dfsEdges(int i, int j)
{

    T[i*102+j] = 0;



    for(int ind= 0; ind<4; ind++)
    {
        int newi = i+diffsi[ind];
        int newj = j + diffsj[ind];

        if(newi < 0 || newi > 101 || newj < 0 || newj > 101)
         continue;

        if(T[newi*102+newj] == 2)
        {
            C.push_back(newi*102+newj);
            dfsEdges(newi,newj);
            return;
        }
    }


}

float mod360(float a)
{
    return a-360.0*floor(a/360.0);

}


float calculateAngle(int ind)
{

    int first = (ind-10+C.size())%C.size();
    int middle = ind;
    int second = (ind+10+C.size())%C.size();

    float ydiff1 = C[first]/102-C[middle]/102;
    float xdiff1 = C[first]%102-C[middle]%102;
    float ydiff2 = C[second]/102-C[middle]/102;
    float xdiff2 = C[second]%102-C[middle]%102;


    float ang1 = atan2(ydiff1,xdiff1);
    float ang2 = atan2(ydiff2,xdiff2);

    float ang = mod360((ang1-ang2)*180.0/3.14159265+360.0*4);

    ang = min(ang,360.0f-ang);

    return ang;


}



int main() {

    cin.tie(NULL);
    std::ios::sync_with_stdio(false);

    int t;
    cin >> t;
    char oneLine[128];

    T.clear();
    T.resize(102*102);

    vector<float> angles;

    for(int testcase = 0; testcase< t; testcase++)
    {
        T.clear();
        T.resize(102*102);
        for(int i = 0; i < 100; i++)
        {
            cin>>oneLine;
            for(int j = 0; j < 100; j++)
                if(oneLine[j] == '1')
                    T[(i+1)*102+j+1] = 1;
        }

        for(int i = 1; i <= 100; i++)
        for(int j = 1; j <= 100; j++)
            if(T[i*102+j] == 0 && has1neighbour(i,j))
                T[i*102+j] = 2;

        for(int i = 1; i <= 100; i++)
        for(int j = 1; j <= 100; j++)
            if(T[i*102+j] == 1 )
                T[i*102+j] = 0;


        C.clear();

/*
        for(int i = 0; i <= 101; i++,cout<<endl)
        for(int j = 0; j <= 101; j++)
            cout<<T[i*102+j];
*/
        bool abort = false;
        for(int i = 0; i <= 101 && !abort; i++)
        for(int j = 0; j <= 101 && !abort; j++)
        {
            if(T[i*102+j] == 2)
            {
                dfsEdges(i,j);
                abort = true;
                break;
            }

        }

//        cout<<C.size()<<endl;

    angles.clear();
        for(int ind = 0; ind < C.size(); ind++)
        {
            angles.push_back(calculateAngle(ind));
            //cout<<ind<<" "<<angles[ind]<<endl;
        }


        int iter = 0;

        float cutoff = 150;
        while(true)
        {
            if(angles[iter] > cutoff && angles[(iter+1)%C.size()] > cutoff && angles[(iter-1+C.size())%C.size()] > cutoff)
                break;

            iter = (iter+1)%C.size();

        }

        int runninglength= 0;
        int anglecount = 0;
        for(int i = 0; i < C.size(); i++)
        {
            if(angles[(iter+i)%C.size()] > cutoff)
            {
                if(runninglength > 3)
                    anglecount++;

                runninglength = 0;
            }
            else
                runninglength++;

        }


        cout<<anglecount<<endl;

    }


}