UVa 12509 : Tin Cutter II

問題リンク : http://uva.onlinejudge.org/external/125/12509.html

問題概要：
n本の線分が与えられる
線分はx軸かy軸に平行である
外側から到達可能な線分の部分の長さの総和を求めたい

解法 :
線分アレンジメント + 座標圧縮 + DFS
線分をアレンジメントして細分化する
細分化した線分の端点 + (それらの前後+-0.5) + 細分化した線分の中心点 を列挙し座標圧縮
どの点にも覆われていないような点からDFSを開始し、線分をまたがないで到達可能な場所を全て見る
それらのうち、線分の中心点に到達できたものを記録しておく
線分の中心に到達できた場合、その線分は最も外側であるのでそれらの線分の長さの総和をとる

コメント :
謎のREが多発した
compute内でメモリを取りすぎていたらしい
boolの2次元配列をすべてvector>にしたら回避できる

コード :

#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-6)
#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 !equals(x,p.x)?x<p.x:(!equals(y,p.y)&&y<p.y); }
  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){}
  bool operator <  (const Segment& s) const { return ( p2 == s.p2 ) ? p1 < s.p1 : p2 < s.p2; }
  bool operator == (const Segment& s) const { return ( s.p1 == p1 && s.p2 == p2 ) || ( s.p1 == p2 && s.p2 == p1 ); }

};

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;
}

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 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)) ) ;
}

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;
}

bool intersectSP(Line s, Point p) { return abs(s.p1-p)+abs(s.p2-p)-abs(s.p2-s.p1) < EPS; }

Point crosspoint(Line l,Line m){
  double A = cross(l.p2-l.p1,m.p2-m.p1);
  double B = cross(l.p2-l.p1,l.p2-m.p1);
  if(abs(A) < EPS && abs(B) < EPS){
    vector<Point> vec;
    vec.push_back(l.p1),vec.push_back(l.p2),vec.push_back(m.p1),vec.push_back(m.p2);
    sort(vec.begin(),vec.end());
    return vec[1];
  }
  return m.p1 + (m.p2-m.p1)*(B/A);
}

typedef pair<int,int> ii;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
vector<Segment> segs;

bool  LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return  equals(a,b) || a < b; } 

Point vir;
bool comp_dist(const Point &a,const Point &b){ return LT(abs(vir-a),abs(vir-b)); }
bool equal_d(const double &a,const double &b) { return equals(a,b); }

struct Double{
  double value;
  bool operator < ( const Double &d ) const { return LT(value,d.value); }
};

void compute(){
  vector<Segment> buf;
  rep(i,segs.size()) {
    vector<Point> vp;
    vp.push_back(segs[i].p1);
    vp.push_back(segs[i].p2);
    rep(j,segs.size()) if( i != j ) {
      if( equals(cross(segs[j].p1-segs[j].p2,segs[i].p1-segs[i].p2),0.0) ) {
        if( onSegment(segs[i].p1,segs[i].p2,segs[j].p1) ) vp.push_back(segs[j].p1);
        if( onSegment(segs[i].p1,segs[i].p2,segs[j].p2) ) vp.push_back(segs[j].p2);
      } else {
        if( intersectSS(segs[i],segs[j]) ) vp.push_back(crosspoint(segs[i],segs[j]));
      }
    }
    sort(vp.begin(),vp.end());
    vp.erase(unique(vp.begin(),vp.end()),vp.end());
    vir = segs[i].p1;
    sort(vp.begin(),vp.end(),comp_dist);
    rep(j,(int)vp.size()-1) buf.push_back(Segment(vp[j],vp[j+1]));
  }

  rep(i,(int)buf.size()) if( !( buf[i].p1 < buf[i].p2 ) ) swap(buf[i].p1,buf[i].p2);
  sort(buf.begin(),buf.end());
  buf.erase(unique(buf.begin(),buf.end()),buf.end());

  vector<double> X,Y;
  rep(i,(int)buf.size()){
    double xL = buf[i].p1.x, xR = buf[i].p2.x;
    double xM = ( xL + xR ) / 2.0;
    X.push_back(xM);
    for(double d=-0.5;LTE(d,0.5);d+=0.5) {
      double nx1 = xL + d, nx2 = xR + d;
      X.push_back(nx1); X.push_back(nx2);    
    }
    double yL = buf[i].p1.y, yR = buf[i].p2.y;
    double yM = ( yL + yR ) / 2;
    Y.push_back(yM);
    for(double d=-0.5;LTE(d,0.5);d+=0.5) {
      double ny1 = yL + d, ny2 = yR + d;
      Y.push_back(ny1); Y.push_back(ny2);
    }
  }
  
  sort(X.begin(),X.end(),LT);
  sort(Y.begin(),Y.end(),LT);
  X.erase(unique(X.begin(),X.end(),equal_d),X.end());
  Y.erase(unique(Y.begin(),Y.end(),equal_d),Y.end());
  map<Double,int> mp_x,mp_y;
  rep(i,(int)X.size()) mp_x[(Double){X[i]}] = i;
  rep(i,(int)Y.size()) mp_y[(Double){Y[i]}] = i;

  int W = mp_x.size(), H = mp_y.size();
  vector<vector<bool> > field(H+5,vector<bool>(W+5,false));
  rep(i,(int)buf.size()) {
    double y1 = buf[i].p1.y, y2 = buf[i].p2.y;
    if( LT(y2,y1) ) swap(y1,y2);
    for(int y=mp_y[(Double){y1}]+1;y<=mp_y[(Double){y2}]+1;y++) {
      double x1 = buf[i].p1.x, x2 = buf[i].p2.x;
      if( LT(x2,x1) ) swap(x1,x2);
      for(int x=mp_x[(Double){x1}]+1;x<=mp_x[(Double){x2}]+1;x++) {
        field[y][x] = true;
      }
    }
  }

  vector<int> MP[H+5][W+5];
  rep(i,(int)buf.size()){
    double x = ( buf[i].p1.x + buf[i].p2.x ) / 2.0, y = ( buf[i].p1.y + buf[i].p2.y ) / 2;
    int ix = mp_x[(Double){x}]+1, iy = mp_y[(Double){y}]+1;
    MP[iy][ix].push_back(i);
  }
  vector<int> reach;
  vector<vector<bool> > visited(H+5,vector<bool>(W+5,false));
  deque<ii> deq;
  deq.push_back(ii(0,0));
  visited[0][0] = true;
  while(!deq.empty()){
    ii cur = deq.front(); deq.pop_front();
    rep(i,4){
      int nx = cur.first + dx[i], ny = cur.second + dy[i];
      if( !( ( 0 <= nx && nx < W+5 ) && ( 0 <= ny && ny < H+5 ) ) ) continue;
      if( visited[ny][nx] ) continue;
      visited[ny][nx] = true;
      if( field[ny][nx] ) { 
        rep(j,(int)MP[ny][nx].size()) reach.push_back(MP[ny][nx][j]);
        continue; 
      }
      deq.push_back(ii(nx,ny));
    }
  }

  sort(reach.begin(),reach.end());
  reach.erase(unique(reach.begin(),reach.end()),reach.end());
  int answer = 0;
  rep(i,reach.size()) answer += (int)abs(buf[reach[i]].p1-buf[reach[i]].p2);
  cout << answer << endl;

}

int main(){
  int T;
  cin >> T;
  while( T-- ){
    int n;
    cin >> n;
    segs.resize(n);
    rep(i,n) cin >> segs[i].p1.x >> segs[i].p1.y >> segs[i].p2.x >> segs[i].p2.y;
    compute();
  }
  return 0;
}