AOJ 2597: Color the Map Extreme

この記事は、AOJ-ICPC Advent Calendarの記事です。

何か名前の"Extreme"ってところがDDRっぽい。
幾何パートは微小なので、本質は枝刈り探索です。選択肢が一番少ない頂点を選ぶ、その中では影響する頂点数が一番多い頂点を選ぶ、次数2以下の頂点を無視する、でかなり速く動きます。
1000点問題のなかではかなり楽なほうです。

#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const double EPS = 1e-7;
const double INF = 1e+10;
const double PI = acos(-1);
//
//
//
int sz[40];
int g[40][40];
vector<Pt>p[40];
int deg[40];
int col;
int now[40];
int n;
int nd;
int dfs(int a){
    if(a==nd)return 1;
    int nx=-1;
    int ch=0;
    int re=0;
    int me=0;
    for(int i=0;i<n;i++){
        if(~now[i])continue;
        if(col==3&&deg[i]<3)continue;
        int mask=0;
        int ef=0;
        for(int j=0;j<n;j++){
            if(g[i][j]){
                if(~now[j])mask|=(1<<now[j]);
                else ef++;
            }
        }
        int nch=__builtin_popcount(mask);
        if(nch==col)return 0;
        if(nch>ch||(nch==ch&&me<ef)){
            nx=i;ch=nch;me=ef;re=mask;
        }
    }
    for(int i=0;i<col;i++){
        if(re&(1<<i))continue;
        now[nx]=i;
        if(dfs(a+1))return 1;
    }
    now[nx]=-1;
    return 0;
}
int main(){
    int a;
    while(scanf("%d",&a),a){
        n=a;
        for(int i=0;i<a;i++){
            p[i].clear();
            int b;
            scanf("%d",&b);
            sz[i]=b;
            for(int j=0;j<b;j++){
                int x,y;
                scanf("%d%d",&x,&y);
                p[i].push_back(Pt(x,y));
            }
            p[i].push_back(p[i][0]);
        }
        for(int i=0;i<a;i++)deg[i]=0;
        for(int i=0;i<a;i++)for(int j=0;j<a;j++)g[i][j]=0;
        for(int i=0;i<a;i++)for(int j=i+1;j<a;j++){
            bool ok=false;
            for(int k=0;k<sz[i];k++)for(int l=0;l<sz[j];l++){
                if(iLL(p[i][k],p[i][k+1],p[j][l],p[j][l+1])!=-1)continue;
                if(iSP(p[i][k],p[j][l],p[i][k+1])==2)ok=true;
                if(iSP(p[i][k],p[j][l+1],p[i][k+1])==2)ok=true;
                if(iSP(p[j][l],p[i][k],p[j][l+1])==2)ok=true;
                if(iSP(p[j][l],p[i][k+1],p[j][l+1])==2)ok=true;
                if((p[i][k]-p[j][l]).ABS()<EPS&&(p[i][k+1]-p[j][l+1]).ABS()<EPS)ok=true;
                if((p[i][k]-p[j][l+1]).ABS()<EPS&&(p[i][k+1]-p[j][l]).ABS()<EPS)ok=true;
            }
            if(ok){
                g[i][j]=g[j][i]=1;
                deg[i]++;deg[j]++;
            }
        }
        int ans=4;
        for(int i=1;i<4;i++){
            col=i;
            for(int j=0;j<a;j++)now[j]=-1;
            nd=n;
            if(i==3){
                for(int j=0;j<a;j++)if(deg[j]<3)nd--;
            }
            if(dfs(0)){
                ans=i;break;
            }
        }
        printf("%d\n",ans);
    }
}