백준 1061, 삼각형

개요

문제 링크
플래 1, Geometry, 컨벡스 헐
한 변을 공유하고 크기가 더 큰 삼각형이 존재하는 삼각형의 개수 구하기

---

접근

1. 까다로운 기하학 문제, 사실 알고리즘 분류를 알기 전까지는 기하학이라는 사실을 알기 매우 어렵다.
2. 우선 세 점의 색이 모두 달라야하므로 R,G,B 좌표는 vector를 이용해 구분해준다. 그리고 "크기가 커질 수 있다"란 무엇일까? 에 대해 고민해보자.
3. 해답은 커질 수 없는 삼각형에 대해 생각하는 것이다. 전체 경우인 R개수 × B개수 × G개수에서 여집합을 구해 빼주면 되는 것인데, 커질 수 없다 = 최대이다 라고 생각하면 생각보다 매우 단순하다. 두 점, 즉 선분에 대해 크기가 최대인 삼각형을 모두 제외해주면 되는 것인데, 다음의 문제가 생긴다.
   1. 선분 RG에 대해 B가 최대점일 수는 있지만, 선분 GB에 대해 R이 최대점이 아닐 수 있다.
   2. 선분 RG에 대해 크기가 최대인 B가 여러개일 수 있다.
4. 따라서 이 문제를 해결해주기 위해 어떤 선분에 대해 삼각형의 크기를 최대로 만드는 점들의 vector를 내보내는 함수를 만들고, 선분 RG의 최대점들 B에 대해 RG-B의 최대크기 = GB-R의 최대크기 = BR-G의 최대크기 임을 만족하는 경우 전체 경우에서 1을 빼주면 된다.
5. 볼록껍질을 사용하는 이유는? 껍질 내부의 점은 항상 최대점이 될 수 없다. 선분이 껍질을 통과하든 통과하지 않든, 항상 더 큰 삼각형을 만드는 점이 껍질에 존재한다.

---

Pseudo code

max_points(line RG) {
    for (Blue)
        if (area(RGB) = max)
            points.push_back(B)
    return points
}

count = Red.size() * Green.size() * Blue.size()

for (Red, Green)
    Blue = max_points(RG)
    for (Blue)
        if (max_area(RG,B) != max_area(GB,R))
            continue
        if (max_area(RG,B) != max_area(BR,G))
            continue
        count--;
return count

---

Source code

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

#define sz size
#define pb push_back
#define pop pop_back
#define all(v) v.begin(),v.end()
#define bb(v) v.back(),v[v.size()-2]
struct pt {
    int y,x;
    bool operator==(pt a) {
        return x==a.x&&y==a.y;
    }
    bool operator!=(pt a){
        return x!=a.x||y!=a.y;
    }
    int operator/(pt a) {
        return x*a.y-y*a.x;
    }
    int ccw(pt b, pt c) {
        pt a = *this;
        return a/b+b/c+c/a;
    }
    int tri(pt b, pt c) {
        pt a = *this;
        return abs(a/b+b/c+c/a);
    }
    bool operator<(pt a) {
        return x<a.x||(x==a.x&&y<a.y);
    }
};
typedef vector<pt> pts;
pts r,g,b,R,G,B;

pts convex(pts p) {
    if (p.sz()<=1) return p;
    sort(all(p));

    pts h1;
    for (pt x:p) {
        while (h1.sz()>=2 && x.ccw(bb(h1))<0)
            h1.pop();
        h1.pb(x);
    }
    reverse(all(p));
    pts h2;
    for (pt x:p) {
        while (h2.sz()>=2 && x.ccw(bb(h2))<0)
            h2.pop();
        h2.pb(x);
    }
    for (pt x:h2) if (find(all(h1),x)==h1.end()) h1.pb(x);
    return h1;
}

pts furth(pt a, pt b, pts C) {
    pts c;
    int m = -1;
    for (pt x:C)
        if (x.tri(a,b)>m)
            m = x.tri(a,b);
    for (pt x:C)
        if (x.tri(a,b)==m)
            c.pb(x);
    return c;
}

int get() {
    int k = r.sz()*g.sz()*b.sz();
    if (!k) return k;
    R = convex(r);
    G = convex(g);
    B = convex(b);
    for (pt r:R)
        for (pt g:G)
            for (pt b:furth(r,g,B)) {
                pt fr = furth(g,b,R)[0];
                int a = b.tri(r,g);
                if (fr.tri(g,b)!=a) continue;
                pt fg = furth(b,r,G)[0];
                if (fg.tri(b,r)!=a) continue;
                k--;
            }
    return k;
}

int main() {
    int n,m;
    cin>>n>>m;
    char c;
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++) {
            cin>>c;
            if (c=='R') r.pb({i,j});
            if (c=='G') g.pb({i,j});
            if (c=='B') b.pb({i,j});
        }
    cout << get();
}