CLASS 6 - P4

1014번: 컨닝 - DP(비트마스킹)

/*
입력된 판을 열을 기준으로 보자. 특정 열의 한 자리에 책상을 놓을 경우, 좌우 열에만 영향을 줄 뿐
같은 열에는 영항을 주지 않음을 알 수 있다. 따라서 n번째 열에 책상을 놓는 경우는 n-1번째 열에만
영향을 받는다. 이때 n~M번째 열에 책상을 놓는 경우는 n+1~M번째 열에 책상을 놓는 경우를 통해 알아
낼 수 있다. 즉 작은 문제를 해결함으로써 그 결과로 큰 문제를 해결할 수 있으므로, 이 문제는 DP로
해결할 수 있다. 각 열에 의자를 놓는 경우의 수는 비트마스크를 이용해 관리하면 된다.
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N, M;
char classroom[11][11];
int dp[10][1024]; //dp[c][s] : c-1번째 열에 책상 집합 s를 배치할 경우의 최댓값

int DP(int c, int s)
{
    if(c == M) return 0;
    if(dp[c][s] != -1) return dp[c][s];
    
    dp[c][s] = 0;
    for(int i=0; i<(1 << N); i++)
    {
        int cnt = 0; //c번째 열에 놓는 책상의 수
        bool chk = true;
        for(int j=0; j<N; j++)
        {
            if(i & (1 << j))
            {
                cnt++;
                if(classroom[j][c] == 'x') chk = false; 
                //책상을 못 놓게 되어 있는 칸과 겹치면 안 된다.
            }
        }
        if(!chk) continue;
        
        bool noCheat[10] = {}; //집합 i처럼 책상을 놓을 경우 다음 열에 놓지 못하는 자리 배열
        char defDest[10]; //입력받은 기존의 다음 열 자리 배열
        for(int j=0; j<N; j++)
        {
            defDest[j] = classroom[j][c+1];
            if(i & (1 << j))
            {
                for(int k=j-1; k<=j+1; k++)
                {
                    if(k >= 0 && k < N) 
                        noCheat[k] = true;
                }
            }
        }
        
        for(int j=0; j<N; j++)
            if(noCheat[j]) classroom[j][c+1] = 'x'; //책상을 놓지 못하는 자리를 전처리
        dp[c][s] = max(dp[c][s], DP(c+1, i) + cnt);
        for(int j=0; j<N; j++) //복구
            classroom[j][c+1] = defDest[j];
    }
    return dp[c][s];
}

void solve()
{
    cin >> N >> M;
    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++)
            cin >> classroom[i][j];
    
    memset(dp, -1, sizeof(dp));
    cout << DP(0, 0) << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int C; cin >> C;
	for(int i=1; i<=C; i++) solve();
}

 

2618번: 경찰차 - DP

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N, W;
pii event[1001];
int dp[1001][1001]; //dp[i][j] : 경찰차 1이 사건 i, 경찰차 2가 사건 j에 있을 때의 최단 경로
pii track[1001][1001];

int solve(int i, int j, int n)
{
    if(n == W+1) return 0;
    if(dp[i][j] != -1) return dp[i][j];
    
    int xi, yi, xj, yj;
    if(i == 0) xi = 1, yi = 1;
    else xi = event[i].first, yi = event[i].second;
    if(j == 0) xj = N, yj = N;
    else xj = event[j].first, yj = event[j].second;
    auto [xn, yn] = event[n];
    
    int ni = abs(xi-xn) + abs(yi-yn);
    int nj = abs(xj-xn) + abs(yj-yn);
    
    int reti = solve(n, j, n+1) + ni;
    int retj = solve(i, n, n+1) + nj;
    if(reti < retj) track[i][j] = {n, j};
    else track[i][j] = {i, n};
    
    return dp[i][j] = min(reti, retj);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> W;
	for(int i=1; i<=W; i++)
	{
	    int x, y; cin >> x >> y;
	    event[i] = {x, y};
	}
	
	memset(dp, -1, sizeof(dp));
	cout << solve(0, 0, 1) << "\n";
	
	int i = 0, j  = 0;
	for(int w=1; w<=W; w++)
	{
	    auto [ni, nj] = track[i][j];
	    if(nj == j) cout << 1 << "\n";
	    else cout << 2 << "\n";
	    i = ni, j = nj;
	}
}

 

3176번: 도로 네트워크 - LCA

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N, K;
vector<pll> graph[100001];
int height[100001];
int par[18][100001]; //부모 희소 배열
ll mn[18][100001], mx[18][100001]; //최소, 최대 희소 배열

void DFS(int u, int p, int h, ll dist)
{
    par[0][u] = p, height[u] = h;
    mn[0][u] = mx[0][u] = dist; //정점 u와 u의 부모와 연결된 간선을 저장
    
    for(auto [d, v] : graph[u])
    {
        if(v == p) continue;
        DFS(v, u, h+1, d);
    }
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
    cin >> N;
    for(int i=1; i<N; i++)
    {
        ll A, B, C; cin >> A >> B >> C;
        graph[A].push_back({C, B});
        graph[B].push_back({C, A});
    }
    
    DFS(1, 0, 0, 1e18);
    mx[0][1] = 0; //최대 희소 배열에서 정점 1(root)에 연결된 가상의 간선을 0으로 설정
    
    for(int i=1; i<18; i++)
    {
        for(int j=1; j<=N; j++)
        {
            par[i][j] = par[i-1][par[i-1][j]];
            mn[i][j] = min(mn[i-1][j], mn[i-1][par[i-1][j]]);
            //f(n)(x) = min(f(n-1)(x), d)와 같은 형태이다. 
            //따라서 거리의 최솟값에 대한 희소 배열을 만들 수 있다.
            mx[i][j] = max(mx[i-1][j], mx[i-1][par[i-1][j]]);
            //마찬가지로 거리의 최댓값에 대한 희소 배열도 만들 수 있다.
        }
    }
    
    cin >> K;
    for(int i=1; i<=K; i++)
    {
        int u, v; cin >> u >> v;
        if(height[u] > height[v]) swap(u, v);
        
        ll mn1 = 1e18, mn2 = 1e18;
        ll mx1 = 0, mx2 = 0;
        int d = height[v] - height[u];
        for(int j=0; j<18; j++)
        {
            if(d & (1 << j))
            {
                mn2 = min(mn2, mn[j][v]); mx2 = max(mx2, mx[j][v]);
                v = par[j][v];
            }
        }
        
        if(u != v)
        {
            for(int j=17; j>=0; j--)
            {
                if(par[j][u] != par[j][v])
                {
                    mn1 = min(mn1, mn[j][u]); mx1 = max(mx1, mx[j][u]);
                    mn2 = min(mn2, mn[j][v]); mx2 = max(mx2, mx[j][v]);
                    u = par[j][u], v = par[j][v];
                }
            }
            mn1 = min(mn1, mn[0][u]); mx1 = max(mx1, mx[0][u]);
            mn2 = min(mn2, mn[0][v]); mx2 = max(mx2, mx[0][v]);
        }
        
        cout << min(mn1, mn2) << " " << max(mx1, mx2) << "\n";
    }
}

 

3653번: 영화 수집 - 세그먼트 트리

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int pn;
int segTree[800001];
int loc[100001]; //loc[i] : DVD의 번호가 i일 때 그 위치

void update(int idx, int n)
{
    idx += pn;
    segTree[idx] = n;
    
    for(idx/=2; idx>=1; idx/=2)
        segTree[idx] = segTree[idx*2] + segTree[idx*2+1];
}

int sum(int l, int r)
{
    l += pn, r += pn;
    int ret = 0;
    while(l <= r)
    {
        if(l%2 == 1) ret += segTree[l++];
        if(r%2 == 0) ret += segTree[r--];
        
        l /= 2, r /= 2;
    }
    return ret;
}

void solve()
{
    memset(segTree, 0, sizeof(segTree));
    int n, m; cin >> n >> m;
    
    pn = 1;
    while(pn < n+m) pn *= 2; //범위 주의
    
    //DVD의 존재를 0, 1로 표현해 세그먼트 트리로 누적합 관리
    for(int i=1; i<=n; i++) 
    {
        loc[i] = n-i;
        update(i-1, 1); 
    }
    
    for(int i=n; i<n+m; i++)
    {
        int dvd; cin >> dvd;
        cout << sum(loc[dvd]+1, i-1) << " ";
        
        update(loc[dvd], 0);
        loc[dvd] = i;
        update(loc[dvd], 1);
    }
    cout << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int T; cin >> T;
	while(T--) solve();
}

 

3679번: 단순 다각형 - 기하(CCW)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef complex<int> coord;

#define X real()
#define Y imag()
int n;
vector<tiii> point;

coord p2v(coord p1, coord p2) { return {p2.X-p1.X, p2.Y-p1.Y}; }
int CCW(coord v1, coord v2) { return (conj(v1)*v2).Y; }

auto cmp = [](tiii t1, tiii t2)
{
    coord p0 = {get<0>(point[0]), get<1>(point[0])};
    coord p1 = {get<0>(t1), get<1>(t1)};
    coord p2 = {get<0>(t2), get<1>(t2)};
    coord v1 = p2v(p0, p1);
    coord v2 = p2v(p0, p2);
    
    int ccw = CCW(v1, v2);
    if(ccw > 0) return true;
    else if(ccw < 0) return false;
    else
    {
        if(v1.X*v1.X+v1.Y*v1.Y < v2.X*v2.X+v2.Y*v2.Y) return true;
        else return false;
    }
};

void solve()
{
    cin >> n;
    //x좌표가 가장 작은 점을 기준으로 CCW 정렬 -> 정렬한 점을 순서대로 출력하면 단순 다각형이 된다.
    for(int i=0; i<n; i++) 
    {
        int x, y; cin >> x >> y;
        point.push_back({x, y, i});
        auto [x0, y0, idx0] = point[0];
        auto [xi, yi, idxi] = point[i];
        if(xi < x0 || xi == x0 && yi < y0) swap(point[i], point[0]);
    }
    sort(point.begin() + 1, point.end(), cmp);
    
    //단, 단순 다각형에서 마지막으로 만든 변에 여러 개의 점이 있을 경우, 역순으로 출력해야 한다.
    int idx = n-1;
    while(true)
    {
        coord p0 = {get<0>(point[0]), get<1>(point[0])};
        coord p1 = {get<0>(point[idx]), get<1>(point[idx])};
        coord p2 = {get<0>(point[idx-1]), get<1>(point[idx-1])};
        coord v1 = p2v(p0, p1);
        coord v2 = p2v(p0, p2);
        
        int ccw = CCW(v1, v2);
        idx--;
        if(ccw != 0) break;
    }
    
    for(int i=0; i<=idx; i++)
    {
        auto [x, y, index] = point[i];
        cout << index << " ";
    }
    for(int i=n-1; i>idx; i--)
    {
        auto [x, y, index] = point[i];
        cout << index << " ";
    }
    cout << "\n";
    
    point.clear();
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int c; cin >> c;
	while(c--) solve();
}

 

5670번: 휴대폰 자판 - 트라이

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N;
string word[100001];
int trie[1000001][26];
bool exist[1000001]; //이 노드까지 도달했을 때 단어가 완성되는지 확인
int childCnt[1000001]; //현재 노드의 자식의 수

int solve(int curNode, int w, int idx)
{
    if(word[w].size() == idx) return 0;
    
    int ret = 0;
    if(trie[curNode][word[w][idx]-'a'] != -1) 
        ret = solve(trie[curNode][word[w][idx]-'a'], w, idx+1);
    
    if(childCnt[curNode] == 1)
    {
        if(curNode == 0 || exist[curNode]) return ret + 1;
        else return ret;
    }
    else return ret + 1;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	while(cin >> N)
	{
	    memset(trie, -1, sizeof(trie));
	    memset(exist, false, sizeof(exist));
	    memset(childCnt, 0, sizeof(childCnt));
	    
	    int node = 1;
	    for(int i=1; i<=N; i++)
	    {
	        cin >> word[i];
	        int curNode = 0;
	        for(int j=0; j<word[i].size(); j++)
	        {
	            if(trie[curNode][word[i][j]-'a'] == -1)
	            {
	                childCnt[curNode]++;
	                curNode = trie[curNode][word[i][j]-'a'] = node++;
	            }
	            else curNode = trie[curNode][word[i][j]-'a'];
	        }
	        exist[curNode] = true;
	    }
	    
	    int ans = 0;
	    for(int i=1; i<=N; i++) ans += solve(0, i, 0);
	    cout << fixed << setprecision(2) << double(ans) / N << "\n";
	}
}

 

11266번: 단절점 - 그래프(DFS 스패닝 트리, BCC)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int V, E;
vector<int> graph[10001];
int DFS_num[10001], DFS_min[10001];
int DFS_cnt = 1;
stack<pii> edge;
bool candi[10001], root[10001];
int childCnt[10001];

void DFS(int u, int p) //u : 정점, p : 정점의 부모
{
    DFS_num[u] = DFS_min[u] = DFS_cnt++;
    for(int v : graph[u])
    {
        if(v == p) continue; //부모를 만나면 무시
        
        if(DFS_num[v]) DFS_min[u] = min(DFS_min[u], DFS_num[v]);
        //이미 방문한 정점을 만났다면(역방향 간선), 해당 정점이 만날 수 있는 정점의 최솟값 갱신
        //DFS_min[v]를 쓰면 다른 BCC에 v가 포함되니 주의
        else
        {
            DFS(v, u); //방문하지 않은 정점을 만났다면(트리 간선), 계속 DFS
            DFS_min[u] = min(DFS_min[u], DFS_min[v]); //최솟값 갱신. 이번에는 DFS_min[v]를 사용
            if(DFS_num[u] <= DFS_min[v]) candi[u] = true;
            //해당 노드의 자식들이 해당 노드의 선조를 만나지 않았다면, 이 노드는 단절점의 후보군이 될 수 있다.
            childCnt[u]++; //노드의 자식 수 세기. 트리 간선 수만 세면 된다.
        }
    }
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> V >> E;
	for(int i=1; i<=E; i++)
	{
	    int A, B; cin >> A >> B;
	    graph[A].push_back(B);
	    graph[B].push_back(A);
	}
	
	for(int i=1; i<=V; i++) //연결 그래프가 아닐 수 있으므로 모든 정점에 대해 DFS
	{
	    if(!DFS_num[i]) 
	    {
	        root[i] = true; //처음 방문한 정점을 루트 처리
	        DFS(i, 0);
	    }
	}
	
	vector<int> ans;
	for(int i=1; i<=V; i++)
	    if(candi[i] && (!root[i] || childCnt[i] >= 2)) //트리의 루트라면 자식의 수가 2개 이상이어야 한다.
	        ans.push_back(i);
	
	cout << ans.size() << "\n";
	for(int i : ans) cout << i << " ";
}

 

11280번: 2-SAT - 3 - SCC(2-SAT)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int SIZE = 20001;
int N, M;
vector<int> graphf[SIZE], graphr[SIZE];
bool vis[SIZE];
stack<int> st;
vector<vector<int>> SCC;
int SCCIdx[SIZE];

int tog(int n) //n을 not n으로 toggle
{
    if(n <= N) return n + N;
    else return n - N;
}

void DFSf(int u)
{
    vis[u] = true;
    for(int v : graphf[u])
        if(!vis[v]) DFSf(v);
    st.push(u);
}

void DFSr(int u)
{
    vis[u] = true;
    SCC.back().push_back(u);
    SCCIdx[u] = SCC.size() - 1; //정점 u가 SCC의 어느 index에 위치하는지 저장
    
    for(int v : graphr[u])
        if(!vis[v]) DFSr(v);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> M;
	for(int i=1; i<=M; i++)
	{
	    int u, v; cin >> u >> v;
	    if(u < 0) u = -u + N;
	    if(v < 0) v = -v + N;
	    
	    graphf[tog(u)].push_back(v); //not u -> v
	    graphf[tog(v)].push_back(u); //not v -> u
	    graphr[v].push_back(tog(u));
	    graphr[u].push_back(tog(v));
	}
	
	for(int i=1; i<=N*2; i++)
	    if(!vis[i]) DFSf(i);
	    
	memset(vis, false, sizeof(vis));
	while(!st.empty())
	{
	    int u = st.top(); st.pop();
	    if(!vis[u])
	    {
	        SCC.emplace_back();
	        DFSr(u);
	    }
	} //코사라주 알고리즘
	
	bool canSCC = true;
	for(int i=1; i<=N; i++)
	{
	    if(SCCIdx[i] == SCCIdx[tog(i)]) //i와 not i가 한 SCC에 있을 수는 없다.
	        canSCC = false;
	}
	
	if(!canSCC) cout << 0;
	else cout << 1;
}

 

11400번: 단절선 - 그래프(DFS 스패닝 트리, BCC)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int SIZE = 100001;
int V, E;
vector<int> graph[SIZE];
int DFS_num[SIZE], DFS_min[SIZE];
int DFS_cnt = 1;
vector<pii> edge;

void DFS(int u, int p)
{
    DFS_num[u] = DFS_min[u] = DFS_cnt++;
    for(int v : graph[u])
    {
        if(v == p) continue;
        
        if(DFS_num[v]) DFS_min[u] = min(DFS_min[u], DFS_num[v]);
        else
        {
            DFS(v, u);
            DFS_min[u] = min(DFS_min[u], DFS_min[v]);
            if(DFS_num[u] < DFS_min[v]) 
            //본래의 BCC 알고리즘에서 이 둘이 같을 때는 역방향 간선이 존재할 때 뿐이다.
            //역방향 간선이 존재하지 않는다면, (u, v)는 단절선이 된다.
            {
                int U = u, V = v;
                if(U > V) swap(U, V);
                edge.push_back({U, V});
            }
        }
    }
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> V >> E;
	for(int i=1; i<=E; i++)
	{
	    int A, B; cin >> A >> B;
	    graph[A].push_back(B);
	    graph[B].push_back(A);
	}
	
	DFS(1, 0);
	
	sort(edge.begin(), edge.end());
	cout << edge.size() << "\n";
	for(auto [u, v] : edge)
        cout << u << " " << v << "\n";
}

 

14939번: 불 끄기 - 완전 탐색

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

bool board[10][10];
bool newboard[10][10];
int dir[2][4] = {{-1, 1, 0, 0}, {0, 0, -1, 1}};
int cnt = 0;
int ans = -1;

void bulb(int x, int y)
{
    newboard[x][y] = !newboard[x][y];
    for(int i=0; i<4; i++)
    {
        int nx = x + dir[0][i];
        int ny = y + dir[1][i];
        
        if(nx >= 0 && nx < 10 && ny >= 0 && ny < 10)
            newboard[nx][ny] = !newboard[nx][ny];
    }
}

void solve(int i)
{
    if(i == 10)
    {
        bool canSolve = true;
        for(int x=0; x<10; x++)
            for(int y=0; y<10; y++)
                if(newboard[x][y]) canSolve = false;
        
        if(canSolve) ans = max(ans, cnt);
        return;
    }

    for(int j=0; j<10; j++)
        if(newboard[i-1][j]) bulb(i, j), cnt++;
    solve(i+1);
}

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

    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            char c; cin >> c;
            if(c == '#') board[i][j] = false;
            else board[i][j] = true;
        }
    }
    
    //맨 윗줄의 스위치를 모든 방법으로 누른다고 가정한다. 2^10-1번이 필요할 것이다.
    //n번째 줄의 전구 상태가 결정되면, n+1번째 줄에 누를 스위치는 자동으로 결정된다.
    //(i-1, j)의 전구가 켜져 있다면 반드시 (i, j)번째 스위치를 눌러야 하기 때문이다.
    //즉 2^10-1번의 반복으로도 문제를 해결할 수 있다.
    for(int i=0; i<(1<<10); i++)
    {
        for(int x=0; x<10; x++)
            for(int y=0; y<10; y++)
                newboard[x][y] = board[x][y];
        
        for(int j=0; j<10; j++)
            if(i & (1 << j)) bulb(0, j), cnt++;
        solve(1);
        cnt=0;
    }
    cout << ans;
}

 

20149번: 선분 교차 3 - 기하(CCW, 선분 교차)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef complex<ld> coord;

#define X real()
#define Y imag()
coord p1, p2, p3, p4;

bool cmp(coord p1, coord p2) { return (p1.X < p2.X || p1.X == p2.X && p1.Y < p2.Y); }
coord p2v(coord p1, coord p2) { return {p2.X-p1.X, p2.Y-p1.Y}; }
ld CCW(coord v1, coord v2) { return (conj(v1)*v2).Y; }
void printCross()
{
    ld p = CCW((p3-p1), (p4-p3)) / CCW((p2-p1), (p4-p3));
    coord ans = p1 + p * (p2-p1);
    cout << fixed << setprecision(10) << ans.X << " " << ans.Y;
} //벡터의 직선의 방정식을 이용한 교차점 구하기

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

    ld x1, y1, x2, y2, x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    p1 = {x1, y1}, p2 = {x2, y2}, p3 = {x3, y3}, p4 = {x4, y4};
    if(cmp(p2, p1)) swap(p1, p2);
    if(cmp(p4, p3)) swap(p3, p4);
    
    coord v12 = p2v(p1, p2), v23 = p2v(p2, p3), v24 = p2v(p2, p4);
    coord v34 = p2v(p3, p4), v41 = p2v(p4, p1), v42 = p2v(p4, p2);
    ld ccw123 = CCW(v12, v23), ccw124 = CCW(v12, v24);
    ld ccw341 = CCW(v34, v41), ccw342 = CCW(v34, v42);
    ld ccw12 = ccw123 * ccw124;
    ld ccw34 = ccw341 * ccw342;
    
    if(ccw12 <= 0 && ccw34 <= 0)
    {
        if(ccw12 == 0 && ccw34 == 0)
        {
            if(cmp(p2, p3) || cmp(p4, p1)) cout << 0;
            else
            {
                cout << 1 << "\n";
                if(ccw123 == 0 && ccw124 == 0 && ccw341 == 0 && ccw342 == 0)
                {
                    if(p1 == p4) cout << p1.X << " " << p1.Y;
                    else if(p2 == p3) cout << p2.X << " " << p2.Y;
                } //네 점이 한 직선 위에 있을 경우, 한 선분의 큰 쪽이 다른 선분의 다른 쪽과 교차해야만 한다.
                else
                {
                    if(p1 == p3 || p1 == p4) cout << p1.X << " " << p1.Y;
                    else if(p2 == p3 || p2 == p4) cout << p2.X << " " << p2.Y;
                } //세 점이 한 직선 위에 있을 경우, 모든 끝점이 교차하는지 확인한다.
            }
        }
        else
        {
            cout << 1 << "\n";
            printCross();
        }
    }
    else cout << 0;
}