TopCoder SRM 449 Div 1
Problem Solving/TopCoder logs 2009. 9. 24. 23:26
어제 밤 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..~ 개인 최장길이 소스 돌파..~ 사실 내용은 별로 없지만..;
Level2 - HexagonalBattlefield
to be updated..
Level3 - StairsColoring
to be updated..
이날따라 너무 피곤해서 비몽사몽간에 치룬 매치이다..~
요즘들어 문제가 계속 어렵게 나오는거같은데.. 그럭저럭 차분하게 풀어서 결국 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 };
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..
'Problem Solving > TopCoder logs' 카테고리의 다른 글
| TopCoder SRM 454 Div 1 (0) | 2009.12.07 |
|---|---|
| TopCoder SRM 453.5 (??) Div 1 (0) | 2009.11.26 |
| [SRM 453] 탑코더 아레나 폭발 -> unrated event (4) | 2009.11.18 |
| TopCoder SRM 450 Div 1 (0) | 2009.10.19 |
| TopCoder Member Pilot 2 (0) | 2009.10.01 |
| TopCoder SRM 448 Div 1 (0) | 2009.09.11 |
| Beta SRM (Member-Run Round) (0) | 2009.08.19 |
| [SRM 446] 매치가 뭐 이래..?! (Unchallengeable Match) (6) | 2009.08.09 |
| TopCoder SRM 445 Div 1 (0) | 2009.07.24 |
| [SRM 444] 개인 역대 최고 등급 경신..~ (0) | 2009.07.09 |