AOJ 1288 : Digits on the Floor

問題リンク : Digits on the Floor | Aizu Online Judge

問題概要 :
線分の情報が与えられる
0から9の数字がそれぞれ何回現れるか数えよ
細かい制約は略

解法 :
最初にunion-findで繋がっている線分をまとめる
各まとまりについて、
各線分の別の線分と交差する回数を求め、昇順にvectorに詰める
このvectorが1,3,6,8の交差回数と同じであればそれがその数字となる
そうでない場合、
vectorが2,5と等しい時、
交差回数が１の線分と繋がっている線分との向きが時計回りであれば２
反時計ま回りであれば５
次に、
線分が別の線分の端点以外で交差するかどうかを確かめ、
交差するのであればそれは4または9
そうでないならば0または7

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0

using namespace std;

class Point{
public:
  double x,y;

  Point(double x = 0,double y = 0): x(x),y(y){}

  Point operator + (Point p){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  bool operator == (const Point& p)const{ return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS; }
};

struct Segment{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
};

typedef Point Vector;
typedef Segment Line;

double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }

double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }

double norm(Point a){ return a.x*a.x+a.y*a.y; }

double abs(Point a){ return sqrt(norm(a)); }

int ccw(Point p0,Point p1,Point p2){
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}

bool intersectSS(Line s, Line t) {
  return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <= 0 &&
         ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2) <= 0;
}

double cross3p(Point p,Point q,Point r) { return (r.x-q.x) * (p.y -q.y) - (r.y - q.y) * (p.x - q.x); }
  
bool collinear(Point p,Point q,Point r) { return fabs(cross3p(p,q,r)) < EPS; }
  
bool ccwtest(Point p,Point q,Point r){ return cross3p(p,q,r) > 0; }
 
bool onSegment(Point p,Point q,Point r){
  return collinear(p,q,r) && equals(sqrt(pow(p.x-r.x,2)+pow(p.y-r.y,2)) + sqrt(pow(r.x-q.x,2) + pow(r.y-q.y,2) ),sqrt(pow(p.x-q.x,2)+pow(p.y-q.y,2)) ) ;
}

int par[1100];

int find(int x){
  if( x == par[x] ) return x;
  return par[x] = find(par[x]);
}

void unit(int x,int y){
  x = find(x), y = find(y);
  if( x != y ) par[x] = y;
}

vector<vector<int> > connect_counter;
int connect[10][6] = {
  {+2,+2,+2,+2,-1,-1},
  {+0,-1,-1,-1,-1,-1},
  {+1,+1,+2,+2,+2,-1},
  {+1,+1,+1,+3,-1,-1},
  {+1,+1,+2,-1,-1,-1},
  {+1,+1,+2,+2,+2,-1},
  {+1,+2,+2,+2,+3,-1},
  {+1,+1,+2,+3,-1,-1},
  {+2,+2,+2,+3,+3,-1},
  {+2,+2,+2,+2,-1,-1}
};

int WhatIsThis(vector<Segment> &segs){
  if( segs.size() == 1 ) return 1;
  vector<int> tmp;
  Segment cur,next;
  rep(i,segs.size()) {
    int cnt = 0;
    Segment touch;
    rep(j,segs.size()) if( i != j ) if( intersectSS(segs[i],segs[j]) ) {
        ++cnt;
        touch = segs[j];
      }
    if( cnt == 1 ) { cur = segs[i], next = touch; }
    assert( cnt );
    tmp.push_back(cnt);
  }
  sort(tmp.begin(),tmp.end());
  if( tmp == connect_counter[3] ) return 3;
  if( tmp == connect_counter[6] ) return 6;
  if( tmp == connect_counter[8] ) return 8;
  if( tmp == connect_counter[2] ) {
    Point p0,p1,p2;
    if( cur.p1 == next.p1 ) p0 = cur.p2, p1 = cur.p1, p2 = next.p2;
    if( cur.p1 == next.p2 ) p0 = cur.p2, p1 = cur.p1, p2 = next.p1;
    if( cur.p2 == next.p1 ) p0 = cur.p1, p1 = cur.p2, p2 = next.p2;
    if( cur.p2 == next.p2 ) p0 = cur.p1, p1 = cur.p2, p2 = next.p1;
    if( ccw(p0,p1,p2) == CLOCKWISE ) return 2;
    else                             return 5;
  }
  bool hasMiddle = false;
  rep(i,segs.size()) rep(j,segs.size()) if( i != j && intersectSS(segs[i],segs[j]) ) {
    if( segs[i].p1 == segs[j].p1 || segs[i].p1 == segs[j].p2 || segs[i].p2 == segs[j].p1 || segs[i].p2 == segs[j].p2 ) continue;
    hasMiddle = true;
    goto Skip;
  }
 Skip:;
  if( tmp == connect_counter[4] ) return (hasMiddle?4:7);
  if( tmp == connect_counter[0] ) return (hasMiddle?9:0);
  return -1;
}

void compute(int n,vector<Segment> &segs){
  vector<int> counter(10,0);
  
  rep(i,n) par[i] = i;
  rep(i,n) REP(j,i+1,n) if( intersectSS(segs[i],segs[j]) ) unit(i,j);
  int dex = 0;
  map<int,int> S;
  rep(i,n) if( !S.count(find(i)) ) S[find(i)] = dex++;
  int V = S.size();
  vector<vector<Segment> > buf(V,vector<Segment>());
  rep(i,n) buf[S[find(i)]].push_back(segs[i]);
  
  rep(i,V) {
    int result = WhatIsThis(buf[i]);
    ++counter[result];
  }

  rep(i,10) {
    if( i ) printf(" ");
    printf("%d",counter[i]);
  } puts("");
}

int main(){
  connect_counter.clear();
  connect_counter.resize(10,vector<int>());
  rep(i,10) rep(j,6) if( connect[i][j] != -1 ) connect_counter[i].push_back(connect[i][j]);
  int n;
  while( cin >> n, n ){
    vector<Segment> segs(n);
    rep(i,n) cin >> segs[i].p1.x >> segs[i].p1.y >> segs[i].p2.x >> segs[i].p2.y;
    compute(n,segs);
  }
  return 0;
}