백준21065 Friendship Circles

작성일 | In

문제 링크

  • https://icpc.me/21065

사용 알고리즘

  • 들로네 삼각분할

시간복잡도

  • $O(N \log N)$

풀이

들로네 삼각분할의 정의에 의해, 삼각분할에서 $p_0$과 같은 삼각형에 속한 점들을 출력하면 됩니다. 즉, 보로노이 다이어그램에서 0번 영역과 인접한 영역의 번호를 출력하면 됩니다.
zigui님 깃허브에 있는 코드를 사용하면 $O(N \log N)$ 시간에 보로노이 다이어그램을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// voronoi diagram : https://github.com/zigui-ps/VoronoiDiagram/blob/master/teamnote_VoronoiDiagram.cpp

void Solve(){
    int n; cin >> n;
    vector<pdd> points(n), vertices;
    vector<pii> edges, areas;
    map<pdd, int> id;
    for(int i=0; i<n; i++) cin >> points[i].first >> points[i].second, id[points[i]] = i;
    voronoi_diagram::solve(points, vertices, edges, areas);
    for(auto &[s,e] : areas) s = id[points[s]], e = id[points[e]];
    vector<int> res;
    for(const auto &[s,e] : areas){
        if(s == 0) res.push_back(e);
        if(e == 0) res.push_back(s);
    }
    sort(res.begin(), res.end());
    cout << res.size() << " ";
    for(auto i : res) cout << i << " ";
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while(T--) Solve();
}