교차점 개수

오늘도 선분 교차 문제를 풀것이다 이건 신기하게 선분 교차 태그가 없다 왜 없을까 난 이문제를 풀기 위해서 ccw를 배웠는데 많조분도 아니고 수학 + 기하다 뭐야 ㅅㅂ 선분 교차 문제가 아니었다;; 문제에서 준 직사각형을 원으로 만드는 문제였다 ㅇㄴ 이게 무슨 골3이란 말인가;;

이 문제는

• 문제의 단순화
• 그걸 수식화

를 하는 졸라 어려운 문제다 직사각형을 원으로 만드는게 정말 미친생각인거 같다

오늘도 문제를 푼다. 어제 푼 선분교차 1문제를 풀고 선분교차 2문제를 봤는데 솔직히 달라진게 없어서 갓지피티 에게 질문을 때렸다.

overlap 검사

오늘 배운것은 overlap 검사다 선분 교차 판정일때 점 4개가 전부 일직선일때 답이 잘못 나올수 있기 때문.

결론

오늘은 결론적으로 ccw를 배웠다. 그리고 선분 교차1을 풀었다?(안풀었을수도) <- (문제내용=선분 교차하는지 안 하는지 검사 하는거임) ccw는 점3개가 있을때 무슨 방향인지 알려주는 알려주는 알고리즘 이였다

S = (x1y2 + x2y3 + x3y1) - (x2y1 + x3y2 + x1y3) S<0 시계 방향, S>0 반시계 방향 S=0 일직선 방향

본론

공식만 외웠을때는 시팔 퍼센트만 알고있지만 증명을 하면 백팔십 퍼센트를 알수있다 난 벡터의 외적을 모르기 때문에 시팔 퍼센트 밖에 모른다 시팔...

하지만 나는 ccw말고 선분 교차1 문제를 풀어야한다 즉 선분이 교차 하는지 안하는지 검사하는 프로그램을 작성해야한다

선분 교차 알고리즘은 블로그를 통해 배웠는데 솔직히 점점 고수준 알고리즘을 보면서 배우는데 블로그를 쓴 사람은 정말 천재인거 같다 그 블로그를 최초로 쓴사람은 정말 천재 아닐까?

난 그렇게 생각한다

그래서 선분 교차를 판정하는 알고리즘 블로그를 본결과

이런 공식이 나왔다 이대로 골드3 하나를 개꿀빨았다 솔직히 이문제를 생각으로 풀려고 한 내가 잘못했다 이런 문제는 과감하게 포기하자

서론

태그를 모르고 실수 하는것은 바보다. 하지만 태그를 알고 실수 하는것은 개쌉바보다 그이유를 결론에서 알아보삼

단연코 세상에서 가장 쉬운 골드 4

걍 딸깍 문제다 못풀리가 없지만 혹시라도 이문제로 bfs를 접해볼꺼라는 사람은 걍 class4나 밀기 바란다. 짜증 나는건 B버튼 구현이 귀찮다는거다 이상없다. 코드 복붙 하려는 사람을 위해 아래에 코드를 제공했다. 아 참고로 실수 하는것도 있는데 x*2 > 99999이면 B버튼을 사용할수 없다

#include <queue>
#include <iostream>
using namespace std;

int n, t, g;
int map[100000];
queue<int> q;

int asd(int x) {
    int xx=x;
    int mul = 1, ans, mod = 0;
    while (true) {
        if (xx/10==0){
            ans = xx % 10;
            if (ans != 0)
                ans--;
            return ans * mul + mod;
        }
        mod += xx % 10 * mul;
        xx /= 10;
        mul*=10;
    }
}

void bfs() {
    q.push(n);
    map[n] = 1;

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        if (x==g){
            cout<<map[x]-1<<"\n";
            return;
        }
        if (map[x+1]==0&&x+1<=99999&&map[x]<t+1){
            q.push(x + 1);
            map[x + 1] = map[x] + 1;
        }

        int b = asd(x * 2);
        if (map[b] == 0 && b <= 99999&&map[x]<t+1&&x*2<=99999) {
            q.push(b);
            map[b]=map[x]+1;
        }
    }
    cout << "ANG\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> t >> g;
    //cout << asd(246) << "\n";
    bfs();
}

https://www.acmicpc.net/problem/7662

솔직히 골드4 인게 이해가 안된다.

왜냐하면 그냥 multiset 쓰면 문제가 실버 3으로 보이기 때문이다.

multiset은 set의 중복이 없는 것이다. 그럼 거의 priority_queue와 비슷해지기 때문이다. 이 문제의 시간 제한은 무려 6초 multiset을 써도 충분히 괜찮다.

코드

#include <set>
#include <iostream>
using namespace std;

int main()
{
    int Test_case;
    cin >> Test_case;

    for (int i = 1; i <= Test_case; i++) {
        int n;
        multiset<int> s;

        cin >> n;
        for (int j = 1; j <= n; j++) {
            int value;
            char order;

            cin >> order >> value;
            if (order == 'I') {
                s.insert(value);
            } else if (order == 'D') {
                if (!s.empty()) {
                    multiset<int>::iterator starting = s.begin();
                    multiset<int>::iterator ending = s.end();
                    ending--;
                    if (value == -1) s.erase(starting);
                    else s.erase(ending);
                }
            }
        }
        if (s.empty()) cout << "EMPTY\n";
        else {
            multiset<int>::iterator starting = s.begin();
            multiset<int>::iterator ending = s.end();
            ending--;
            cout << *(ending) << " " << *(starting) << "\n";
        }
    }
}

일단 가장 첫번째로 점화식이 하나 있다. 연구를 하다 보면 이것에 규칙이 있다는것을 알게될 것이고 그게 곧 점화식으로 표현이 된다. 다이나믹 프로그래밍 이기 때문이다

aₙ₊₁ = aₙ₋₁ + aₙ₋₅

이런 점화식이 있지만 눈치가 빨랐다면 의문이 생길것이다.

1부터 5까지는 어케 구함?

그러므로 1부터 5까지는 수시로 값을 집어 넣어 줘어야 한다.

개인적으로 말하지만 실버3는 풀이는 거의 다 간단하지만 생각이 오래 걸리는거 같다.

코드

#include <vector>
#include <iostream>
using namespace std;

int main()
{
    long long test_case;
    vector<long long> v;

    v.push_back(1);
    v.push_back(1);
    v.push_back(1);
    v.push_back(2);
    v.push_back(2);

    for (int i = 5; i < 100; i++) {
        v.push_back(v.at(i - 5) + v.at(i - 1));
    }

    cin >> test_case;
    for (int i = 1; i <= test_case; i++) {
        long long n;
        cin >> n;
        cout << v.at(n - 1) << "\n";
    }
}

이 코드를 쓰게되면 맞는다.