앳코더90 - 009 - Three Point Angle（★6）

https://atcoder.jp/contests/typical90/tasks/typical90_i

009 - Three Point Angle（★6）

 

문제는 간단하다. 

푸는 방법을 모를뿐

 

좌표가 N개 주어진다. 이중 3개를 골라서 3개의 각이 가장 크게하라.

기하학 문제고 가장 쉽게 생각나는 방법은 브루트포스로 3개를 고르는것이다.

하지만 이는 NC3으로 O(N^3) 으로 시간초과가 난다.

정해역시 모르겠으니 에디토리얼을 참고하며 이 방법을 구현해보자.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const ll INF = 100000000000;
const double pi = 3.14159265358979;
const ll MOD = 1000000007;

struct Point
{
    double py;
    double px;
};

Point operator-(const Point& a1, const Point& a2) 
{
    return Point{ a1.px - a2.px, a1.py - a2.py };
}

int N;
Point v[2002];
double ans = -1;

double getangle(Point G) 
{
    if (G.py >= 0.0) 
    {
        double I = G.px / sqrt(G.px * G.px + G.py * G.py);
        double kaku = acos(I) * 180.0 / pi;
        return kaku;
    }
    else 
    {
        double I = G.px / sqrt(G.px * G.px + G.py * G.py);
        double kaku = acos(I) * 180.0 / pi;
        return 360.0 - kaku;
    }
    //lA•B| = |A| |B| cos a
}

double getangle2(double I1, double I2) 
{
    double res = abs(I1 - I2);
    if (res >= 180.0) 
        return 360.0 - res;
    return res;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> v[i].py >> v[i].px;
    }

    cout << fixed << setprecision(12);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < N; k++)
            {
                if (i == j || i == k || j == k) 
                    continue;

                double I1 = getangle(v[i] - v[j]);
                double I2 = getangle(v[k] - v[j]);
                ans = max(ans, getangle2(I1, I2));
            }
        }
    }

    cout << ans;

    //https://atcoder.jp/contests/typical90/editorial/1149
    

    return 0;

}

 

N^3브루트 포스 안의 코드들을 살펴보자

getangle()은 편각을 구하는 코드다.

I1, I2는 각각 편각을 의미한다.

그리고 주석에 적혀있는 내용과 같이 
lA•B| = |A| |B| cos a

내적을 이용하여 해당 수식을 이용하여 각을 구한다.

 

그렇게 구한 두개의 편각을 getangle2() 함수를 이용하여 세 점을 이루는 각을 구한다.

이 방법외에도 tan를 이용한 방법등으로 세 점 사이의 각을 구할 수 있다.

하지만 결과적으로 N^3으로 시간초과가 났다.

 

일본어 에디토리얼을 보면서 이해할려했지만 기하학적 지식이 부족하고 일본어 실력도 부족하여 일단 비슷한 백준문제가 나올때 다시오기로 결심했다. 정해는 N^2logN으로 각하나를 고정시켜놓고 lower_bound로 후보를 탐색하는 방식인것 같다. 하지만 세부적인 디테일을 이해하기 어려웠다.