[C++] 백준 11758 - CWW(계산 기하, vector, vector2, 구조체)

0. [c++] 백준

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

1. 풀이

1) 

2)

3)

2. 소스코드

- ver1

#include<iostream>
#include<vector>
 
using namespace std;
 
vector<pair<double, double> > V;
 
int main() {
    double a, b;
    for (int i = 0; i < 3; i++) {
        cin >> a >> b;
 
        V.push_back({ a,b });
    }
 
    V.push_back(V[0]);
 
    a = 0; b = 0;
 
    for (int i = 0; i < 3; i++) {
        a += V[i].first * V[i + 1].second;
        b += V[i + 1].first * V[i].second;
    }
 
    double ret = (a - b);
 
    if (ret > 0) {
        cout << 1 << endl;
    }
    else if (ret < 0) {
        cout << -1 << endl;
    }
    else
        cout << 0 << endl;
 
    return 0;
}

- ver 2(이런저런 함수 붙어있음)

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
 
using namespace std;
 
const double PI = 2.0 * acos(0.0);
 
struct vector2
{
    double x, y;
    explicit vector2(double x_, double y_) :x(x_), y(y_) {}
    bool operator == (const vector2& rhs) const {
        return (x == rhs.x && y == rhs.y);
    }
    bool operator < (const vector2& rhs) const {
        return (x != rhs.x ? x < rhs.x : y < rhs.y);
    }
    vector2 operator + (const vector2& rhs) const {
        return vector2(x + rhs.x, y + rhs.y);
    }
    vector2 operator - (const vector2& rhs) const {
        return vector2(x - rhs.x, y - rhs.y);
    }
    vector2 operator * (double rhs) const {
        return vector2(x * rhs, y * rhs);
    }
 
    //벡터의 길이를 반환한다.
    double norm() const { return hypot(x, y); }
    //방향이 같은 단위 벡터를 반환한다.
    vector2 normalize() const {
        return vector2(x / norm(), y / norm());
    }
    //x축의 양의 방향으로부터 이 벡터까지의 반시계방향으로 잰 각도
    double polar() const { return fmod(atan2(y, x) + 2 * PI, 2 * PI); }
    //내적,외적의 구현
    double dot(const vector2& rhs) const {
        return  x * rhs.x + y * rhs.y;
    }
    double cross(const vector2& rhs) const {
        return x * rhs.y - y * rhs.x;
    }
    //이 벡터를 rhs에 사영한 결과
    vector2 project(const vector2& rhs) const {
        vector2 r = rhs.normalize();
        return r * r.dot(*this);
    }
 
};
 
//++문제에 따라 추가해야 할 함수
 
//double형의 실수형 오류 방지
bool relativeEqual(double a, double b) {
    double diff = fabs(a - b);
    if (diff < 1e-10)return true;
    return diff <= 1e-8 * max(fabs(a), fabs(b));
}
 
//두 벡터의 사이각(세타)
double Interval(vector2 a, vector2 b) {
    return acos(a.dot(b) / a.norm() * b.norm());
}
 
//단순 다각형 p의 넓이를 구한다.
double area(const vector<vector2>& p) {
    double ret = 0;
    for (int i = 0; i < p.size(); i++)
    {
        int j = (i + 1) % p.size();
        ret += p[i].x * p[j].y - p[j].x * p[i].y;
    }
    return fabs(ret) / 2.0;
}
 
//3개의 점에서 a가 b보다 얼마나 p에 가까운지 반환하는 함수
double howMuchCloser(vector2 p, vector2 a, vector2 b) {
    return (b - p).norm() - (a - p).norm();
}
 
//위의 과정을 2개의 실수를 활용해 표현하는 방법
double howMuchCloser22(double px, double py, double ax, double ay, double bx, double by) {
    return sqrt((bx - px) * (bx - px) + (by - py) * (by - py)) - sqrt((ax - px) * (ax - px) + (ay - py) * (ay - py));
}
 
 
 
//코드 15.2 두 벡터의 방향성을 판단하는 ccw() 함수의 구현
 
//원점에서 벡터 b가 벡터 a의 반시계 방향이면 양수, 시계 방향이면 음수,
//평행이면 0을 반환한다.
double ccw(vector2 a, vector2 b) {
    return a.cross(b);
}
 
//점 p를 기준으로 벡터 b가 벡터 a의 반시계 방향이면 양수, 시계 방향이면 음수,
//평행이면 0을 반환한다.
double ccw(vector2 p, vector2 a, vector2 b) {
    return ccw(a - p, b - p);
}
 
 
int main() {
 
    double x, y;
    cin >> x >> y;
    vector2 a(x, y);
    cin >> x >> y;
    vector2 b(x, y);
    cin >> x >> y;
    vector2 p(x, y);
 
    if (ccw(p, a, b) > 0)
        cout << 1;
    else if (ccw(p, a, b) < 0)
        cout << -1;
    else
        cout << 0;
 
    return 0;
}

3. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.517~525.

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!