13092022-04-18 19:47:08k_balintJáték a síkoncpp14Accepted 100/10018ms4300 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=5005;

int n,tt;
vector<int> adj[c];
int vis[c],par[c];
bool A[c],ans[c];
map<pair<int,int>,int> m;
int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
pair<int,int> arr[c];

bool novel(int v){
    if(vis[v]==tt) return 0;
    vis[v]=tt;
    for(int x:adj[v]){
        if(vis[x]==tt) continue;
        if(par[x]==x){
            par[v]=x; par[x]=v;
            return 1;
        }
        else{
            vis[x]=tt;
            if(novel(par[x])){
                par[v]=x; par[x]=v;
                return 1;
            }
        }
    }
    return 0;
}

void magyar(){
    for(int i=1;i<=n;i++) par[i]=i;
    tt=1;
    for(int i=1;i<=n;i++){
        if(A[i] && par[i]==i){
            ++tt; novel(i);
        }
    }
}

void edg(int i){
    for(int j=0;j<4;j++){
        int nx=arr[i].first+xx[j]; int ny=arr[i].second+yy[j];
        auto it=m.find(make_pair(nx,ny));
        if(it!=m.end()){
            adj[i].push_back(it->second);
            adj[it->second].push_back(i);
        }
    }
}

void dfsa(int v){
    vis[v]=tt;
    if(A[v]) ans[v]=1;
    for(int x:adj[v]){
        if(vis[x]==tt) continue;
        if((A[v] && par[v] != x) || (!A[v] && par[v]==x)) dfsa(x);
    }
}

void dfsb(int v){
    vis[v]=tt;
    if(!A[v]) ans[v]=1;
    for(int x:adj[v]){
        if(vis[x]==tt) continue;
        if((!A[v]&&par[v]!=x)|| (A[v]&&par[v]==x)) dfsb(x);
    }
}

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

    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b; cin>>a>>b;
        arr[i]=make_pair(a,b);
        m[arr[i]]=i; edg(i);
        A[i]=(a+b)&1;
    }

    magyar();
    for(int i=1;i<=n;i++){
        if(par[i]==i){
            ++tt;
            if(A[i]) dfsa(i);
            else dfsb(i);
        }
    }

    int cnt=0;
    for(int i=1;i<=n;i++) {
        if(ans[i]) ++cnt;
    }
    cout << cnt << '\n';
    for(int i=1;i<=n;i++){
        if(ans[i]) cout << arr[i].first << ' ' << arr[i].second << '\n';
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms2148 KiB
2Accepted3ms2380 KiB
subtask29/9
3Accepted1ms2224 KiB
4Accepted1ms2236 KiB
subtask310/10
5Accepted1ms2244 KiB
6Accepted1ms2248 KiB
7Accepted1ms2256 KiB
8Accepted1ms2252 KiB
9Accepted1ms2248 KiB
10Accepted1ms2260 KiB
11Accepted1ms2264 KiB
12Accepted1ms2268 KiB
subtask410/10
13Accepted2ms2380 KiB
14Accepted2ms2400 KiB
15Accepted2ms2420 KiB
16Accepted2ms2572 KiB
subtask516/16
17Accepted2ms2572 KiB
18Accepted2ms2576 KiB
19Accepted2ms2592 KiB
20Accepted2ms2620 KiB
21Accepted2ms2500 KiB
subtask618/18
22Accepted2ms2492 KiB
23Accepted2ms2516 KiB
24Accepted2ms2664 KiB
25Accepted2ms2672 KiB
26Accepted2ms2688 KiB
subtask737/37
27Accepted4ms3400 KiB
28Accepted4ms3344 KiB
29Accepted14ms3704 KiB
30Accepted18ms3792 KiB
31Accepted16ms3860 KiB
32Accepted4ms3788 KiB
33Accepted4ms3256 KiB
34Accepted8ms3280 KiB
35Accepted8ms3272 KiB
36Accepted6ms3936 KiB
37Accepted8ms4000 KiB
38Accepted6ms4072 KiB
39Accepted8ms4172 KiB
40Accepted8ms4188 KiB
41Accepted8ms4284 KiB
42Accepted12ms4300 KiB