AOJ 0237: Last Door

最近、問題解くのに時間かけすぎな気もしますが...

あんまりバシバシ解けるタイプでも無いので, そうなれるようにちょっとずつ変わって行きたい所存です.

ちなみにこれ解けてません. 三角関数まわりの誤差でしょうか.

強連結成分分解は間違ってないはずです.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
 
#define MAX_N (128)
#define EPS (1e-5)
#define SQ(X) ((X) * (X))
#define EQ(a, b) (fabs(a - b) <= EPS)
#define D1 (-1)
#define D2 (1)
#define ONLINE (0)
 
using namespace std;
 
class Triangle {
    public:
        double x[3], y[3];
        int no;
};
 
class Point {
    public:
        double x, y;
         
        Point operator - (Point &a){
            Point ret;
            ret.x = x - a.x;
            ret.y = y - a.y;
            return (ret);
        }
};
 
vector<int> G[MAX_N];
vector<int> rG[MAX_N];
vector<int> compress[MAX_N];
vector<int> vs;
bool used[MAX_N];
bool group[MAX_N];
int cmp[MAX_N];
int N;
 
void addEdge(int from, int to)
{
    G[from].push_back(to);
    rG[to].push_back(from);
}
 
void dfs(int v)
{
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++){
        if (!used[G[v][i]]){
            dfs(G[v][i]);
        }
    }
    vs.push_back(v);
}
 
void revDfs(int v, int k)
{
    used[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); i++){
        if (!used[rG[v][i]]){
            revDfs(rG[v][i], k);
        }
    }
}
 
int scc()
{
    int ret;
    memset(used, 0, sizeof(used));
    vs.clear();
     
    for (int i = 0; i < N; i++){
        if (!used[i]){
            dfs(i);
        }
    }
     
    memset(used, 0, sizeof(used));
     
    ret = 0;
    for (int i = vs.size() - 1; i >= 0; i--){
        if (!used[vs[i]]){
            revDfs(vs[i], ret++);
        }
    }
     
    for (int i = 0; i < N; i++){
        for (int j = 0; j < G[i].size(); j++){
            if (cmp[i] != cmp[G[i][j]]){
                compress[cmp[G[i][j]]].push_back(cmp[i]);
            }
        }
    }
     
    return (ret);
}
 
double inProduct(Point a, Point b)
{
    return (a.x * b.x + a.y * b.y);
}
 
double getSize(Point a)
{
    return (sqrt(SQ(a.x) + SQ(a.y)));
}
 
int checkCross(Point p1, Point p2, Point p3)
{
    Point vecA = p2 - p1, vecB = p3 - p1;
    double D = vecA.x * vecB.y - vecB.x * vecA.y;
    if (EQ(0, D)){
        return (ONLINE);
    }
    else if (D > 0){
        return (D1);
    }
    return (D2);
}
 
void judgeAdj(Triangle a, Triangle b, double dist)
{
    double len;
    Point p[4];
     
    len = 0.0;
    for (int i = 0; i < 3; i++){
        for (int j = i + 1; j < 3; j++){
            if (len < SQ(a.x[i] - a.x[j]) + SQ(a.y[i] - a.y[j])){
                len = SQ(a.x[i] - a.x[j]) + SQ(a.y[i] - a.y[j]);
                p[0].x = a.x[i], p[0].y = a.y[i];
                p[1].x = a.x[j], p[1].y = a.y[j];
            }
        }
    }
    //printf("%lf %lf %lf %lf\n", p[0].x, p[0].y, p[1].x, p[1].y);
    Point e, sa;
     
    e.x = 0, e.y = 1;
    sa = p[0] - p[1];
    double theta = acos(inProduct(e, sa) / (getSize(e) * getSize(sa)));
    if (fabs(theta - M_PI) < EPS){
        theta = 0;
    }
    //printf("theta = %lf\n", theta);
     
    p[2].x = p[0].x + dist * cos(theta), p[2].y = p[0].y + dist * sin(theta);
    p[3].x = p[1].x + dist * cos(theta), p[3].y = p[1].y + dist * sin(theta);
     
    bool cross = false;
     
    for (int i = 0; i < 3; i++){
        bool judge = true;
        Point k;
        k.x = b.x[i], k.y = b.y[i];
        judge &= (checkCross(p[0], p[1], k) * checkCross(p[2], p[3], k) <= 0);
        judge &= (checkCross(p[0], p[2], k) * checkCross(p[1], p[3], k) <= 0);
        cross |= judge;
    }
     
    if (cross == true){
        //printf("hoge, %d, %d\n", a.no, b.no);
        addEdge(a.no, b.no);
    }
     
}
 
int main()
{
    int n, d;
    Triangle data[128];
     
    while (1){
         
        scanf("%d%d", &n, &d);
         
        N = n;
        if (n + d == 0){
            break;
        }
         
        for (int i = 0; i < n; i++){
            data[i].no = i;
            for (int j = 0; j < 3; j++){
                scanf("%lf%lf", &data[i].x[j], &data[i].y[j]);
            }
        }
         
        for (int i = 0; i < n; i++){
            G[i].clear();
            rG[i].clear();
            compress[i].clear();
        }
         
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if (i != j){
                    judgeAdj(data[i], data[j], d);
                }
            }
        }
         
        int k = scc();
         
        int ans = 0;
        memset(used, 0, sizeof(used));
         
        for (int i = 0; i < k; i++){
            if (compress[i].size() == 0){
                ans++;
            }
        }
         
        printf("%d\n", ans);
    }
     
    return (0);
}