전 정말 썼었어요ㅠㅠ...

임의로 모든 점들의 인덱스가 x값 순서대로 1...N으로 매겨져 있다고 가정합시다. 그럼 문제를 아래와 같이 재해석 할 수 있습니다:

(A) 각 레이저의 자취는 x축값이 증가하는 방향으로 움직이는 레이저가 지나간 점들과, 그 자취에 속한 점들을 x값 순서대로 이어주는 선분으로 이루어져있습니다.
(B) 두 레이저가 만나는 1번째 점과 N번째 점을 제외하고는 항상 한 개의 자취에 속하게 됩니다.

문제에서의 조건에 따라 같은 x좌표를 갖는 점이 유일하게 존재하고 두 개의 자취가 서로 교차하지 않기 때문에, 상대적으로 위쪽에 있는 자취와 아래쪽에 있는 자취로 (사람이) 명확히 구분할 수 있습니다. 이를 각각 upperchain과 lowerchain이라고 부르도록 하겠습니다.

각 점을 x값 순서대로 upperchain에 넣을지 lowerchain에 넣을지를 고려하도록 하는 동적계획법을 생각해 볼 수 있습니다.

D[n][i][j] := index n번째 점까지 고려하여, upperchain의 가장 끝 점은 i이며 lowerchain의 가장 끝 점은 j일때의 경우의 수.

이제 n+1번째 점을 i와 잇는지(upperchain의 연장) j와 잇는지(lowerchain의 연장)를 결정해야합니다.

이때, 이러한 각각의 연결이 upperchain 혹은 lowerchain의 정의를 깨트리지는 않는지 확인해야합니다. 이를 위해 프로그램이 이해할 수 있도록 upperchain과 lowerchain을 정의해보겠습니다. 가능한 방법은 많지만 제가 했던 방법을 소개하려합니다 :) (다른 쉽거나 재밌는 아이디어가 있으시면 알려주세요)

upperchain의 정의 : upperchain에 속하는 임의의 한 선분 e (x1,y1)-(x2,y2) [이때 x1<x2]와 lowerchain에 속하는 점들 중 x값이 x1 ~ x2 사이인 모든 점들 p에 대해서 (x1,y1)-(x2,y2)-(px,py)의 방향은 시계방향을 따른다. (아래의 그림을 참조해주세요)

lowerchain의 정의는 upperchain의 그것을 조금만 바꾸면 얻을 수 있습니다. 이제 n+1번째점이 upperchain의 끝점 i와 이어진다면, i+1부터 n까지의 점들은 모두 lowerchain에 속하리라 짐작할수 있고 i->n+1->k (i+1<=k<=n)의 방향이 모두 시계방향임을 확인한다면 이것은 유효한 확장이라고 볼 수 있습니다.

즉, D[n][i][j]의 값이 0 이상 일때

1. i+1...n까지의 점이 i->n+1을 잇는 선분에서 봤을때 모두 시계방향이면 D[n+1][n+1][j] 값이 D[n][i][j]만큼 증가한다.

2. j+1...n까지의 점이 j->n+1을 잇는 선분에서 봤을때 모두 반시계방향이면 D[n+1][i][n+1]값이 D[n][i][j]만큼 증가한다.

   다만 위의 정의는 각 점 n+1이 둘 중 한 개의 자취에만 속한다는 가정에 따른 것이기 때문에, 두 자취 모두에 속해야하는 N번째 점에 대해서는 예외가 필요합니다. 임의로 먼저 upperchain이 N번째 점에 먼저 도달했다고 가정을 하고, lowerchain이
   t에 있을때 t와 N을 이어도 문제가 없는지를 검사해서 이를 합산하면 답이 될 것입니다.

   마지막으로, (1)(2)를 관찰하면 D[n][i][j]값중 값이 존재하는 n,i,j는 항상 ( n=i 또는 n=j ) 와 ( i,j<=n )을 만족시킴을 알 수 있습니다. 그러므로 실제 테이블에서는 D[i][j]만을 남기고 n=max(i,j)라고 마음 속에(그리고 프로그램 속에) 남겨두시면 시간과 공간복잡도를 줄일 수 있습니다. 이때의 시간 복잡도는 O(n^3)이 됩니다.

#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
LL D[50][50];
pii P[50];
int N;
int xross(int a, int b, int c)
{
        LL A = P[b].first - P[a].first;
        LL B = P[b].second - P[a].second;
        LL C = P[c].first - P[a].first;
        LL D = P[c].second - P[a].second;
        LL R = A * D - B * C;
        if (R<0) return -1;
        if (R>0) return 1;
        return 0;
}
int lowergood(int i, int j)
{
        int q;
        for (q=i+1;q<j;q++) if( xross(i, j, q) <= 0 ) return 0;
        return 1;
}
int uppergood(int i, int j)
{
        int q;
        for (q=i+1;q<j;q++) if( xross(i, j, q) >= 0) return 0;
        return 1;
}
int main()
{
        int T;
        scanf("%d", &T);
        for (;T;T--)
        {
                scanf("%d", &N);
                int q, w, k;
                for (q=0;q<N;q++) scanf("%d %d", &P[q].first, &P[q].second);
                for (q=0;q<N;q++) for(w=0;w<N;w++) D[q][w]=0;
                sort(P, P+N);
                D[1][0] = D[0][1] = 1;
                for (k=1;k+1<N;k++)
                {
                        for (q=0;q<k;q++)
                        {
                                D[k+1][q] += D[k][q];
                                if (lowergood(q, k+1)) D[k][k+1]+=D[k][q];
                                if (uppergood(q, k+1)) D[k+1][k]+=D[q][k];
                                D[q][k+1] += D[q][k];
                        }
                }
                LL ans=0;
                for (q=0;q<N;q++) if (uppergood(q,N-1)) ans += D[q][N-1];
                cout << ans << endl;
        }
        return 0;
}