[코드포스 Practice19] E. Tell Your World

코포 장난하나! 왤케 어려워!! 싶은 문제 였는데 점 세 개만 비교하면 돼서 안도했다.

 

이걸 어떻게 하면 점 세 개만 써도 된다는 생각이 떠오를까

 

암튼,, 점 두개는 직선 만들고 하나는 다른 점과 비교하는 용도로 쓰면 될거라 생각했다.

 

 

 

그런데 기울기 구하는 부분에서 문제였다. y차에서 x차를 나눠야 하는데 그럼 실수값이 되버리고 만다.

 

분명 실수끼리 비교하면 소숫점 때문에 문제 생길텐디

 

북님한테 물어보니 기약분수로 나눈 다음 분모 곱해서 정수로 비교하면 된다고 했다.

 

아 근데 또 기약분수가 문제였다. 좀 생각해보니 최대 공약수로 나누면 되겠다 싶었음.

 

최대공약수... 지금까지 4번은 쓴 듯

 

하지만 아직까지 기억 못하고 있음

 

눈 닿는 곳에 적어두면 언젠가 외우겠지

 

 

코드는 이렇게 짰다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
#define xx first
#define yy second

i64 GCD(i64 n1, i64 n2)
{
    if (n2 == 0)
        return n1;
    return GCD(n2, n1 % n2);
}

bool check(ii64 p1, ii64 p2, ii64 p3, vector<i64> v)
{
    // cout << p1.yy << " " << p2.yy << " " << p3.yy << endl;
    
    i64 res = GCD((p2.yy - p1.yy), (p2.xx - p1.xx));
    i64 a = (p2.yy - p1.yy) / res;
    i64 b = (p2.xx - p1.xx) / res;
    i64 k = b*p2.yy - a*p2.xx;
    
    if (b*p3.yy == a*p3.xx + k)
        return false;
    
    if(v.size() <= 4)
        return true;
    
    for (int i = 4; i < v.size(); i++)
    {
        bool line = true;
        bool point = true;

        res = GCD((v[i] - p3.yy), (i - p3.xx));
        i64 c = (v[i] - p3.yy) / res;
        i64 d = (i - p3.xx) / res;
        
        // cout << a << " " << b << " " << c << " " << d << endl << endl;
        
        if (b*v[i] != a*i + k)
            line = false;
        
        if (a*d != c*b)
            point = false;
            
        if (!line && !point)
            return false;
    }
    
    
    return true;
}

int main() {
    int n;
    scanf("%d", &n);
    
    vector<i64> v(n+1);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &v[i]);
    
    bool is_ok = false;
    ii64 p1, p2, p3;
    
    p1.xx = 1; p1.yy = v[1];
    p2.xx = 2; p2.yy = v[2];
    p3.xx = 3; p3.yy = v[3];
    
    if (check(p1, p2, p3, v)) 
        is_ok = true;
    
    if (check(p1, p3, p2, v)) 
        is_ok = true;
    
    if (check(p2, p3, p1, v)) 
        is_ok = true;
    
    if (is_ok)
        cout << "Yes";
    else
        cout << "No";
        
    return 0;
}

중간에 이런 경우 빼먹어서 한 번 고쳤다

 

그런데 또 틀렸음ㅋㅋ

 

이 경우가 틀렸는데 그림으로 그려보면 이렇다

 

내 로직으로는 이렇게 밖에 판단 못 한다.

 

이거 보니깐 일주일 전에 북님이 집합 만들어서 집합이 두 개면 true 아니면 false라는게 떠올랐다

 

왜이리 잘 까먹지?? 다시 짜야겠다 

 

nnn

nㅜㅜ

ㅜ 아 모르겠다 함수 너무 어려워

 

ㅜㅜ ㅜ

ㅜㅜ

눈물나

 

위처럼 생각해서 아래처럼 코드 짰는데 틀렸고 이젠 어떻게 할지 모르겠다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
#define xx first
#define yy second

i64 GCD(i64 n1, i64 n2)
{
    if (n2 == 0)
        return n1;
    return GCD(n2, n1 % n2);
}

bool check(ii64 p1, ii64 p2, ii64 p3, vector<i64> v)
{
    i64 res = GCD((p2.yy - p1.yy), (p2.xx - p1.xx));
    i64 a = (p2.yy - p1.yy) / res;
    i64 b = (p2.xx - p1.xx) / res;
    i64 k1 = b*p2.yy - a*p2.xx;
    
    if (v.size() == 4)
    {
        if (b*p3.yy == a*p3.xx + k1)
            return false;
        return true;
    }
    
    set <i64> s;
    s.insert(k1);
    cout << "k1 : " << k1 << endl;
    for (int i = 4; i < v.size(); i++)
    {
        res = GCD((v[i] - p3.yy), (i - p3.xx));
        i64 c = (v[i] - p3.yy) / res;
        i64 d = (i - p3.xx) / res;
        i64 k2 = d*v[i] - c*i;
        cout << "k2 : " << k2 << endl;
        
        s.insert(k2);
    }
    
    cout << s.size() << endl;
    
    if (s.size() == 2)
        return true;
    return false;
}

int main() {
    int n;
    scanf("%d", &n);
    
    vector<i64> v(n+1);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &v[i]);
    
    bool is_ok = false;
    ii64 p1, p2, p3;
    
    p1.xx = 1; p1.yy = v[1];
    p2.xx = 2; p2.yy = v[2];
    p3.xx = 3; p3.yy = v[3];
    
    if (check(p1, p2, p3, v)) 
        is_ok = true;
    
    if (check(p1, p3, p2, v)) 
        is_ok = true;
    
    if (check(p2, p3, p1, v)) 
        is_ok = true;
    
    if (is_ok)
        cout << "Yes";
    else
        cout << "No";
        
    return 0;
}

 

그냥 풀이 볼래.. 너무 오래 고민했고 이젠 답답함

 

ㅋㅋㅋ 슬프게도 풀이 봐도 모르겠다

 

내일 물어봐야지..

 

 

어ㄴ ㅡ부분이 어렵냐면

 

처음에 원점이랑 기울기 구하고 마지막에 y[2] - y[1] 기울기 저장한 부분이랑

 

처음에 원점이랑 기울기 구한 것도 잘 모르겠고..

 

여러모로 눈물 흘린 문제다... 

 

ㅠ ㅠㅠ ㅠ 어려워

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int n;
    scanf("%d", &n);
    
    vector<i64> y(n);
    for (int i = 0; i < n; i++)
        scanf("%lld", &y[i]);
        
    vector<ii64> d;
    d.emplace_back(1, y[1] - y[0]);
    d.emplace_back(2, y[2] - y[0]);
    d.emplace_back(1, y[2] - y[1]);
    
    for (auto &di : d)
    {
        auto dx = di.xx;
        auto dy = di.yy;
        
        set <i64> coef;
        
        for (int x = 0; x < n; x++)
            coef.insert(dx * y[x] - dy * (x+1));
        
        if (coef.size() == 2)
        {
            printf("Yes");
            return 0;
        }
    }
    
    printf("No");
    
    return 0;
}

 

휴 설명 들었다

 

위의 기울기 다 구한 건 필요 없었고 세 개만 있으면 됐었다.

 

기울기 다 구한 다음에 각 점에 대해 c값 구한 다음 집합에 넣는다.