SRM490 Div2 Hard(1000) Hieroglyphs
x,yの範囲が狭いので全探索。そのままでは間に合わないので線分を座標別に分けておくことで計算量を減らす。
#include <string> #include <vector> #include <sstream> using namespace std; struct SEGMENT { int x1, y1, x2, y2; }; vector<SEGMENT> read( vector<string> s ) { vector<SEGMENT> v; for ( int i=0; i<(int)s.size(); i++ ) { stringstream ss( s[i] ); while ( true ) { SEGMENT g; ss >> g.x1 >> g.y1 >> g.x2 >> g.y2; v.push_back( g ); if ( ss.eof() ) break; else ss.ignore( 1 ); } } return v; } class Hieroglyphs{public: int minimumVisible( vector <string> hier1, vector <string> hier2 ) { const int L = 80; vector<SEGMENT> h1 = read( hier1 ); vector<SEGMENT> h2 = read( hier2 ); // h2を水平・垂直位置別に分ける vector<SEGMENT> h2h[L+1]; vector<SEGMENT> h2v[L+1]; for ( int i=0; i<(int)h2.size(); i++ ) { if ( h2[i].x1 == h2[i].x2 ) h2v[h2[i].x1].push_back( h2[i] ); if ( h2[i].y1 == h2[i].y2 ) h2h[h2[i].y1].push_back( h2[i] ); } // 重複を含めた長さ int total = 0; for ( int i=0; i<(int)h1.size(); i++ ) total += h1[i].x2-h1[i].x1 + h1[i].y2-h1[i].y1; for ( int i=0; i<(int)h2.size(); i++ ) total += h2[i].x2-h2[i].x1 + h2[i].y2-h2[i].y1; int ans = 99999999; for ( int dx=-L; dx<=L; dx++ ) for ( int dy=-L; dy<=L; dy++ ) { int l = total; for ( int i=0; i<(int)h1.size(); i++ ) { if ( h1[i].x1 == h1[i].x2 && 0 <= h1[i].x1+dx && h1[i].x1+dx <= L ) for ( int j=0; j<(int)h2v[h1[i].x1+dx].size(); j++ ) l -= max( min(h1[i].y2+dy,h2v[h1[i].x1+dx][j].y2) - max(h1[i].y1+dy,h2v[h1[i].x1+dx][j].y1), 0 ); if ( h1[i].y1 == h1[i].y2 && 0 <= h1[i].y1+dy && h1[i].y1+dy <= L ) for ( int j=0; j<(int)h2h[h1[i].y1+dy].size(); j++ ) l -= max( min(h1[i].x2+dx,h2h[h1[i].y1+dy][j].x2) - max(h1[i].x1+dx,h2h[h1[i].y1+dy][j].x1), 0 ); } ans = min( ans, l ); } return ans; }};