UNKNOWN //************************************** // Name: acmp.ru 571 task solution // Description:Educational // By: Pavel Sakau // // // Inputs:None // // Returns:None // //Assumes:None // //Side Effects:None //This code is copyrighted and has limited warranties. //Please see http://www.Planet-Source-Code.com/xq/ASP/txtCodeId.13766/lngWId.3/qx/vb/scripts/ShowCode.htm //for details. //************************************** #include <stdlib.h> #include <stdio.h> #include <vector> #include <algorithm> using namespace std; #define NameIn "input.txt" #define NameOut "output.txt" #define Infinity 1000000000 #define X 0 #define Y 1 #define H 2 #define MAX_HEIGHT_SEGMENTS 3000 #define MAX_SUM_SIZE 3000 typedef short int int16; struct Point { int coord[3]; Point( int x = 0, int y = 0, int h = 0 ) { coord[X] = x ; coord[Y] = y ; coord[H] = h ; } }; struct TriangleSegment { int16 coord[2]; int16 direction; TriangleSegment( int x = 0, int y = 0, int dir = 0 ) { coord[X] = x ; coord[Y] = y ; direction = dir ; } }; typedef vector<TriangleSegment> Segments; int16** Sum[2]; Segments seg[MAX_HEIGHT_SEGMENTS]; int N = 0 ; int Answer = 0 ; vector <int> Way; /* 5 6 \/ 4 - - 1 /\ 32 */ int moves[3][6] = { {1, 1, 0,-1,-1, 0}, {1, 0,-1,-1, 0, 1}, {0,-1,-1, 0, 1, 1} } ; int populateSwitch[6] = {0, 5, 0, 0, 0, 1} ; int sumUpdate[6] = {0, 0, 0, 0, 0, 1} ; int sumShift[2][2] = { {-1, 0}, {0, -1} } ; Point MinPoint; void DataIn() { FILE* FileIn = fopen( NameIn, "r" ) ; fscanf( FileIn, "%d\n", &N ); for (int i = 0; i < N; i++) { int move; fscanf( FileIn, "%d", &move ); Way.push_back( move - 1 ); } fclose( FileIn ); } void DataOut() { FILE* FileOut = fopen( NameOut, "w" ) ; fprintf( FileOut, "%d\n", Answer ); fclose( FileOut ); } void CountShift() { Point cur; for (int i = 0; i < N; i++) { for (int j = 0; j < 3; j++) { cur.coord[j] += moves[j][Way[i]] ; if (MinPoint.coord[j] > cur.coord[j]) MinPoint.coord[j] = cur.coord[j] ; } } } void PopulateSegments() { Point cur( abs(MinPoint.coord[X]), abs(MinPoint.coord[Y]), abs(MinPoint.coord[H]) ); for (int i = 0; i < N; i++) { if (Way[i] == 4 || Way[i] == 5) seg[cur.coord[H]].push_back( TriangleSegment( cur.coord[X], cur.coord[Y], Way[i] ) ); if (Way[i] == 1 || Way[i] == 2) seg[cur.coord[H] - 1].push_back( TriangleSegment( cur.coord[X], cur.coord[Y], Way[i] ) ); for (int j = 0; j < 3; j++) cur.coord[j] += moves[j][Way[i]]; } } TriangleSegment MoveSegment( TriangleSegment segment ) { return TriangleSegment( segment.coord[X] + moves[X][segment.direction], segment.coord[Y] + moves[Y][segment.direction], (segment.direction + 3)%6 ); } TriangleSegment GetLeftSegment( TriangleSegment segment ) { if (segment.direction == 2 || segment.direction == 4) return MoveSegment( segment ); return segment; } TriangleSegment GetRightSegment( TriangleSegment segment ) { if (segment.direction == 1 || segment.direction == 5) return MoveSegment( segment ); return segment; } TriangleSegment GetDownSegment( TriangleSegment segment ) { if (segment.direction == 1 || segment.direction == 2) return MoveSegment( segment ); return segment; } TriangleSegment GetUpSegment( TriangleSegment segment ) { if (segment.direction == 4 || segment.direction == 5) return MoveSegment( segment ); return segment; } bool CompareSegments( TriangleSegment a, TriangleSegment b ) { TriangleSegment left = GetLeftSegment( a ) ; TriangleSegment right = GetRightSegment( b ) ; TriangleSegment right2 = GetLeftSegment( b ) ; return ((right.coord[X] - left.coord[X] == right.coord[Y] - left.coord[Y]) && (right.coord[X] - left.coord[X] > 0)) || ((right2.coord[X] - left.coord[X] == right2.coord[Y] - left.coord[Y]) && (right2.coord[X] - left.coord[X] > 0)) ; } void SortSegments() { for (int i = 0; i < MAX_HEIGHT_SEGMENTS; i++) sort( seg[i].begin(), seg[i].end(), CompareSegments ); } void CreateAndInitSums() { for (int i = 0; i < 2; i++) { Sum[i] = new int16*[MAX_SUM_SIZE] ; for (int j = 0; j < MAX_SUM_SIZE; j++) { Sum[i][j] = new int16[MAX_SUM_SIZE] ; for (int k = 0; k < MAX_SUM_SIZE; k++) Sum[i][j][k] = 0 ; } } } void PopulateSums() { for (int i = 0; i < MAX_HEIGHT_SEGMENTS; i++) { int curSegLength = seg[i].size() ; for (int j = 0; j < curSegLength; j++) if (j%2 == 0) { TriangleSegment left = GetLeftSegment( seg[i][j] ) ; TriangleSegment right = GetRightSegment( seg[i][j + 1] ) ; Point cur( left.coord[X], left.coord[Y], 0 ); int direction = left.direction ; while (cur.coord[X] != right.coord[X] || cur.coord[Y] != right.coord[Y]) { if (sumUpdate[direction] == Y) Sum[sumUpdate[direction]][cur.coord[X]][cur.coord[Y]] = 1 ; else Sum[sumUpdate[direction]][cur.coord[Y]][cur.coord[X]] = 1 ; for (int k = 0; k < 3; k++) cur.coord[k] += moves[k][direction] ; direction = populateSwitch[direction] ; } } } } void PreprocessSums() { for (int i = 0; i < 2; i++) for (int j = 0; j < MAX_SUM_SIZE; j++) for (int k = 1; k < MAX_SUM_SIZE; k++) Sum[i][j][k] += Sum[i][j][k - 1] ; } int GetSumX( int y, int end, int begin ) { if (begin < 0) return Sum[X][y][end]; return Sum[X][y][end] - Sum[X][y][begin]; } int GetSumY( int x, int end, int begin ) { if (begin < 0) return Sum[Y][x][end]; return Sum[Y][x][end] - Sum[Y][x][begin] ; } void CountSolutionsNaive() { for (int i = 0; i < MAX_HEIGHT_SEGMENTS; i++) { int curSegLength = seg[i].size() ; for (int j = 0; j < curSegLength; j++) if (j%2 == 0) { TriangleSegment leftDown = GetDownSegment( seg[i][j] ) ; TriangleSegment rightDown = GetDownSegment( seg[i][j + 1] ) ; int dist = rightDown.coord[X] - leftDown.coord[X] ; for (int k = 1; k <= dist; k++) for (int pos = 0; pos < dist - k + 1; pos++) { TriangleSegment left( leftDown.coord[X] + pos, leftDown.coord[Y] + pos, 0 ); TriangleSegment right( left.coord[X] + k, left.coord[Y] + k, 0 ); if (right.coord[X] - k >= 0) if (GetSumX( right.coord[Y], right.coord[X] - 1, right.coord[X] - k - 1 ) + GetSumY( left.coord[X], left.coord[Y] + k - 1, left.coord[Y] - 1) == 2*k) Answer++; } TriangleSegment leftUp = GetUpSegment( seg[i][j] ) ; TriangleSegment rightUp = GetUpSegment( seg[i][j + 1] ) ; dist = rightUp.coord[X] - leftUp.coord[X] ; for (int k = 1; k <= dist; k++) for (int pos = 0; pos < dist - k + 1; pos++) { TriangleSegment left( leftUp.coord[X] + pos, leftUp.coord[Y] + pos, 0 ); TriangleSegment right( left.coord[X] + k, left.coord[Y] + k, 0 ); if (rightUp.coord[Y] - k >= 0) if (GetSumX( left.coord[Y], left.coord[X] + k - 1, left.coord[X] - 1 ) + GetSumY( right.coord[X], right.coord[Y] - 1, right.coord[Y] - k - 1) == 2*k) Answer++; } } } } int GetDist( TriangleSegment a, TriangleSegment b ) { return min( abs(a.coord[X] - b.coord[X]), abs(a.coord[Y] - b.coord[Y]) ) ; //return max( abs(a.coord[X] - b.coord[X]), abs(a.coord[Y] - b.coord[Y]) ) + 3 ; } void CountSolutions() { for (int i = 0; i < MAX_HEIGHT_SEGMENTS; i++) { int curSegLength = seg[i].size() ; for (int j = 0; j < curSegLength; j++) if (j%2 == 0) { TriangleSegment left = GetLeftSegment( seg[i][j] ) ; TriangleSegment right = GetRightSegment( seg[i][j + 1] ) ; TriangleSegment cur( left.coord[X], left.coord[Y], left.direction ); int direction = left.direction ; while (cur.coord[X] != right.coord[X] || cur.coord[Y] != right.coord[Y]) { if (cur.coord[X] + moves[X][direction] == right.coord[X] && cur.coord[Y] + moves[Y][direction] == right.coord[Y]) break; int dist = GetDist( cur, right ); int l = 0 ; int r = dist ; while (l + 1 < r) { int mid = (l + r)/2 ; if (direction == 5) { TriangleSegment midPoint( cur.coord[X], cur.coord[Y] + mid ) ; if ( GetSumX( midPoint.coord[Y], midPoint.coord[X] + mid - 1, midPoint.coord[X] - 1 ) + GetSumY( midPoint.coord[X], midPoint.coord[Y] - 1, midPoint.coord[Y] - mid - 1 ) == mid*2 ) l = mid ; else r = mid ; } else { TriangleSegment midPoint( cur.coord[X] + mid, cur.coord[Y] ) ; if ( GetSumX( midPoint.coord[Y], midPoint.coord[X] - 1, midPoint.coord[X] - mid - 1 ) + GetSumY( midPoint.coord[X], midPoint.coord[Y] + mid - 1, midPoint.coord[Y] - 1 ) == mid*2 ) l = mid ; else r = mid ; } } if (direction == 5) { TriangleSegment midPoint( cur.coord[X], cur.coord[Y] + r ) ; if ( GetSumX( midPoint.coord[Y], midPoint.coord[X] + r - 1, midPoint.coord[X] - 1 ) + GetSumY( midPoint.coord[X], midPoint.coord[Y] - 1, midPoint.coord[Y] - r - 1 ) == r*2 ) l = r ; } else { TriangleSegment midPoint( cur.coord[X] + r, cur.coord[Y] ) ; if ( GetSumX( midPoint.coord[Y], midPoint.coord[X] - 1, midPoint.coord[X] - r - 1 ) + GetSumY( midPoint.coord[X], midPoint.coord[Y] + r - 1, midPoint.coord[Y] - 1 ) == r*2 ) l = r ; } Answer += l ; for (int k = 0; k < 2; k++) cur.coord[k] += moves[k][direction] ; direction = populateSwitch[direction] ; cur.direction = direction ; } } } } void SolveProblem() { CountShift(); PopulateSegments(); SortSegments(); CreateAndInitSums(); PopulateSums(); PreprocessSums(); //CountSolutionsNaive(); CountSolutions(); } int main() { DataIn(); SolveProblem(); DataOut(); return 0; }