어제 밤 12시에 열린 매치..~
이날따라 너무 피곤해서 비몽사몽간에 치룬 매치이다..~
요즘들어 문제가 계속 어렵게 나오는거같은데.. 그럭저럭 차분하게 풀어서 결국 1문제 를 풀어냈다..~
250은 별로 어려운 문제가 아니었는데 생각하는데 좀 오래걸렸고..
결정적으로 오타를 못찾아서 낮은 점수에 머물렀다..
그리고 나서 500을 열려고보니.. 550점!!! 그래서 950을 열까 하다가 시간이 얼마 안남아서 그냥 포기했다..~
결국 rating 은 +17 에 만족.. 컨디션만 좀 좋았으면 챌도 좀 했을텐데 좀 아쉽군..






Level1 - MaxTriangle
삼각형의 세 점의 (x, y)가 좌표가 모두 integer 이고 그 중 두변의 길이가 sqrt(A), sqrt(B) 인 삼각형중 가장 넓이가 큰 삼각형 찾기..

한참동안 해법을 못찾아서 당황했다.. 무슨 원의 방정식 찾고 점을 각도만큼 회전이동하고.. binary search, ternary search 도 생각해보고 했는데.. 결국.. 찾아낸방법은.. 모든 integer 좌표를 brute force로 찾아서 그중 가능한 젤 큰 삼각형만 구하면 되는것이었다.. -_-;;

삼각형 중 한 점은 (0, 0) 으로 고정시키고 나머지 점은 모든 x 에 대해 피타고라스의 정리를 이용하여 y를 찾는다.. 이렇게 만들어진 가능한 모든 (x, y) 쌍에 대해서 삼각형의 넓이를 구하면 된다.. 삼각형 넓이는 벡터 외적연산을 이용하였다..~

문제 자체는 별게 없지만.. 사실 precision error, overflow 등 때문에 좀 주의를 기울여야 한다..
의외로 많은 사람이 system test fail 한 것을 보면 알 수 있다..

149 line..~ 개인 최장길이 소스 돌파..~ 사실 내용은 별로 없지만..;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <cmath>
  7 using namespace std;
  8 //#define min(x, y) ((x) > (y) ? (y) : (x))
  9 #define max(x, y) ((x) > (y) ? (x) : (y))
 10 //#define INF 999999999
 11 #define EPS 1e-16
 12
 13 typedef struct _p {
 14     double x, y;
 15 } POINT;
 16
 17 double get_area(POINT* pt, int n)
 18 {
 19     int i;
 20     double a, b, sum;
 21     sum = 0.0;
 22     for (i = 1; i <= n; i++) {
 23         a = (pt[i-1].x * pt[i%n].y);
 24         b = (pt[i%n].x * pt[i-1].y);
 25         sum += (a - b);
 26     }
 27     sum *= 0.5;
 28     if (sum < 0.0)
 29         return -1.0 * sum;
 30     return sum;
 31 }
 32
 33 class MaxTriangle {
 34 public:
 35
 36 double calculateArea(int A, int B)
 37 {
 38     int x1, y1, x2, y2;
 39     int i, temp, sq;
 40     int j, temp2, sq2;
 41     double max1, area;
 42     POINT pt[4];
 43     x1 = y1 = x2 = y2 = 0;
 44     max1 = -1;
 45     for (i = 0; i*i <= A; i++) {
 46         temp = A - i * i;
 47         if (temp < i*i)
 48             break;
 49         sq = (int)(sqrt((double)temp) + EPS);
 50         if (sq * sq == temp) {
 51             x1 = sq;
 52             y1 = i;
 53             for (j = 0; j*j <= B; j++) {
 54                 temp2 = B - j*j;
 55                 if (temp2 < j*j)
 56                     break;
 57                 sq2 = (int)(sqrt((double)temp2) + EPS);
 58                 if (sq2 * sq2 == temp2) {
 59                     x2 = sq2;
 60                     y2 = j;
 61                     pt[0].x = 0;
 62                     pt[0].y = 0;
 63                     pt[1].x = x1;
 64                     pt[1].y = y1;
 65                     pt[2].x = x2;
 66                     pt[2].y = y2;
 67                     pt[3].x = 0;
 68                     pt[3].y = 0;
 69                     area = get_area(pt, 3);
 70                     max1 = max(area, max1);
 71                     pt[0].x = 0;
 72                     pt[0].y = 0;
 73                     pt[1].x = x1;
 74                     pt[1].y = y1;
 75                     pt[2].x = y2;
 76                     pt[2].y = x2;
 77                     pt[3].x = 0;
 78                     pt[3].y = 0;
 79                     area = get_area(pt, 3);
 80                     max1 = max(area, max1);
 81                     pt[0].x = 0;
 82                     pt[0].y = 0;
 83                     pt[1].x = x1;
 84                     pt[1].y = y1;
 85                     pt[2].x = -x2;
 86                     pt[2].y = -y2;
 87                     pt[3].x = 0;
 88                     pt[3].y = 0;
 89                     area = get_area(pt, 3);
 90                     max1 = max(area, max1);
 91                     pt[0].x = 0;
 92                     pt[0].y = 0;
 93                     pt[1].x = x1;
 94                     pt[1].y = y1;
 95                     pt[2].x = -y2;
 96                     pt[2].y = -x2;
 97                     pt[3].x = 0;
 98                     pt[3].y = 0;
 99                     area = get_area(pt, 3);
100                     max1 = max(area, max1);
101                     pt[0].x = 0;
102                     pt[0].y = 0;
103                     pt[1].x = x1;
104                     pt[1].y = y1;
105                     pt[2].x = -x2;
106                     pt[2].y = y2;
107                     pt[3].x = 0;
108                     pt[3].y = 0;
109                     area = get_area(pt, 3);
110                     max1 = max(area, max1);
111                     pt[0].x = 0;
112                     pt[0].y = 0;
113                     pt[1].x = x1;
114                     pt[1].y = y1;
115                     pt[2].x = -y2;
116                     pt[2].y = x2;
117                     pt[3].x = 0;
118                     pt[3].y = 0;
119                     area = get_area(pt, 3);
120                     max1 = max(area, max1);
121                     pt[0].x = 0;
122                     pt[0].y = 0;
123                     pt[1].x = x1;
124                     pt[1].y = y1;
125                     pt[2].x = x2;
126                     pt[2].y = -y2;
127                     pt[3].x = 0;
128                     pt[3].y = 0;
129                     area = get_area(pt, 3);
130                     max1 = max(area, max1);
131                     pt[0].x = 0;
132                     pt[0].y = 0;
133                     pt[1].x = x1;
134                     pt[1].y = y1;
135                     pt[2].x = y2;
136                     pt[2].y = -x2;
137                     pt[3].x = 0;
138                     pt[3].y = 0;
139                     area = get_area(pt, 3);
140                     max1 = max(area, max1);
141                 }
142             }
143         }
144     }
145 printf("max1 = %lf\n", max1);
146     return max1;
147 }
148
149 };



Level2 - HexagonalBattlefield



to be updated..



Level3 - StairsColoring



to be updated..


Leave a Comment


to Top