어제 저녁 8시에 열렸던 매치..~
그동안 조금씩 조금씩 레이팅을 올려왔는데.. 어제 매치로 어느덧 옐로우까지 올라갔다..~
맨 처음에 얼떨결에 옐로우 한번 찍어보고.. 거의 2년만에 다시한번 찍었다.. -_-
이거 여기까지 올라오는것도 힘들었는데.. 레드는 도대체 어떻게 달성하는거임?


사용자 삽입 이미지
사용자 삽입 이미지



[250] IncredibleMachine
input으로 여러개의 좌표가 주어진다.. x는 증가방향 y는 감소 방향.. 각 연속되는 좌표를 이어서 여러개의 slope를 만들수 있다.. 맨 처음 좌표에서 공을 굴려서 맨 마지막 좌표로 떨어지게할때.. 맨 마지막 좌표에 T초에 떨어졌다고 할 때, 이 행성의 중력이 얼마인지 구하기..

흐미.. 완전 제대로 물리 문제가 나왔다.. -_-

이 문제는 전형적인 binary search로 풀수 있다..~
일단 중력 g에 대해서 binary search 하면서 고정시키고
그때 맨 끝점에 도착했을때의 시간을 구한다.. 이 시간을 T에 가깝게 근접시키면 된다..

이때 다음과 같은 공식을 알아야 한다.. (다 고딩때 배웠던거.. -_-)

a = g * sin(alpha)
v = v0 * t + a * t
s = v0 * t + 1/2 * a * t^2

그리고 근의공식도 알아야한다..

a * x^2 + b * x + c  = 0 의 해는
(-b +(또는 -) sqrt(b^2 - 4 * a * c)) / (2 * a)

예전에 floating point number에 대해서 binary search하다가 어이없이 틀린적이 있어서.. (여기)
이제는 bsearch 종료조건을 오차한계로 하지않고 그냥 300번 돌렸다.. ㅎㅎ

이 문제를 풀다가 어이없던거는..
중간에 sin(theta)를 구해야되는데 그냥 (높이/빗변) 하면 그게 sin(theta)인데..
좌표를 가지고 힘들게 각도 구해서 sin(각도) 로 구했다는거.. -_-;;
아놔.. 도대체 내가 뭐한거야..


  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 PI acos(-1.0)
 12 #define EPS 1e-12
 13
 14 typedef struct _point {
 15     double x, y;
 16 } POINT;
 17 POINT pt[200];
 18
 19 double get_dist(POINT p1, POINT p2)
 20 {
 21     return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
 22 }
 23
 24 double get_angle2(POINT p)
 25 {
 26     double x, y, temp;
 27     x = p.x;
 28     y = p.y;
 29     if (y == 0) {
 30         if (x >= 0)
 31             return 0;
 32         else
 33             return PI;
 34     }
 35     if (x == 0) {
 36         if (y >= 0)
 37             return 0.5*PI;
 38         else
 39             return 1.5*PI;
 40     }
 41     temp = atan(fabs(y/x));
 42     if (x > 0 && y > 0)
 43         return temp;
 44     if (x < 0 && y > 0)
 45         return PI-temp;
 46     if (x > 0 && y < 0)
 47         return 2.0*PI-temp;
 48     return temp+PI;
 49 }
 50
 51 class IncredibleMachine {
 52 public:
 53
 54 double gravitationalAcceleration(vector <int> x, vector <int> y, int T)
 55 {
 56     int n;
 57     int it, i;
 58     double left, right, mid;
 59     double t, v0, ang, a, d;
 60     double sum;
 61     POINT p1;
 62
 63     n = x.size();
 64     for (i = 0; i < n; i++) {
 65         pt[i].x = x[i];
 66         pt[i].y = y[i];
 67     }
 68     left = 0.0;
 69     right = 1000000000.0;
 70     it = 300;
 71     while (it--) {
 72         mid = (left + right) * 0.5;
 73         v0 = 0;
 74         sum = 0;
 75         for (i = 1; i < n; i++) {
 76             d = get_dist(pt[i], pt[i-1]);
 77             p1.x = pt[i].x - pt[i-1].x;
 78             p1.y = pt[i].y - pt[i-1].y;
 79             ang = get_angle2(p1);
 80             ang = 2.0 * PI - ang;
 81             a = mid * sin(ang);
 82             //a = mid / sin(ang);
 83
 84             t = (-1.0 * v0 + sqrt(v0*v0 + 4.0 * 0.5 * a * d)) / a;
 85             sum += t;
 86             v0 = v0 + a * t;
 87         }
 88         if (sum > T) {
 89             left = mid;
 90         }
 91         else {
 92             right = mid;
 93         }
 94     }
 95     return mid;
 96 }
 97
 98 };




[500] MazeWandering
2차원 grid가 주어지고 각 cell은 empty이거나 wall이다.. empty인 cell중에 하나에는 치즈가 있다.. 이때 치즈를 먹기위에 이동해야하는 move의 개수의 기대값 구하기.. (모든 cell에 대해 각각을 시작위치로 생각하고 구해서 평균을 구해야함)


to be updated..



[1000] SquareFreeSets



to be updated..


to Top