4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: struct PenLift 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: typedef pair<int, int> point; 4fd800b3a8 2011-02-23 kinaba: typedef map< point, set<point> > graph; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int numTimes( vector<string> segments, int n ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: // Determine All Significant Coordinates 4fd800b3a8 2011-02-23 kinaba: set<int> xs, ys; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<segments.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: stringstream sin(segments[i]); 4fd800b3a8 2011-02-23 kinaba: int x1, y1, x2, y2; sin >> x1 >> y1 >> x2 >> y2; 4fd800b3a8 2011-02-23 kinaba: xs.insert(x1); 4fd800b3a8 2011-02-23 kinaba: xs.insert(x2); 4fd800b3a8 2011-02-23 kinaba: ys.insert(y1); 4fd800b3a8 2011-02-23 kinaba: ys.insert(y2); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // Construct the graph, separated by all significant coordinates 4fd800b3a8 2011-02-23 kinaba: graph G; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<segments.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: stringstream sin(segments[i]); 4fd800b3a8 2011-02-23 kinaba: int x1, y1, x2, y2; sin >> x1 >> y1 >> x2 >> y2; 4fd800b3a8 2011-02-23 kinaba: if( x1 == x2 ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: set<int>::iterator it = ys.lower_bound(min(y1,y2)); 4fd800b3a8 2011-02-23 kinaba: set<int>::iterator ed = ys.upper_bound(max(y1,y2)); 4fd800b3a8 2011-02-23 kinaba: for(set<int>::iterator pv=it++; it!=ed; ++it,++pv) 4fd800b3a8 2011-02-23 kinaba: G[point(x1,*pv)].insert(point(x1,*it)), 4fd800b3a8 2011-02-23 kinaba: G[point(x1,*it)].insert(point(x1,*pv)); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: else 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: set<int>::iterator it = xs.lower_bound(min(x1,x2)); 4fd800b3a8 2011-02-23 kinaba: set<int>::iterator ed = xs.upper_bound(max(x1,x2)); 4fd800b3a8 2011-02-23 kinaba: for(set<int>::iterator pv=it++; it!=ed; ++it,++pv) 4fd800b3a8 2011-02-23 kinaba: G[point(*pv,y1)].insert(point(*it,y1)), 4fd800b3a8 2011-02-23 kinaba: G[point(*it,y1)].insert(point(*pv,y1)); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // count the number of odd vertices (/2) per connected components 4fd800b3a8 2011-02-23 kinaba: set<point> vis; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int cnt = 0; 4fd800b3a8 2011-02-23 kinaba: for(graph::iterator s=G.begin(); s!=G.end(); ++s) 4fd800b3a8 2011-02-23 kinaba: if( !vis.count(s->first) ) 4fd800b3a8 2011-02-23 kinaba: cnt += max(1, numOdd(s->first, G, vis, n)/2); 4fd800b3a8 2011-02-23 kinaba: return cnt - 1; // first touch do not require a pen-lift 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // simple dfs 4fd800b3a8 2011-02-23 kinaba: int numOdd( point p, graph& G, set<point>& vis, int n ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( vis.count(p) ) 4fd800b3a8 2011-02-23 kinaba: return 0; 4fd800b3a8 2011-02-23 kinaba: vis.insert(p); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int cnt = G[p].size()*n % 2; // if odd degree then 1 else 0 4fd800b3a8 2011-02-23 kinaba: for(set<point>::iterator it=G[p].begin(); it!=G[p].end(); ++it) 4fd800b3a8 2011-02-23 kinaba: cnt += numOdd(*it, G, vis, n); 4fd800b3a8 2011-02-23 kinaba: return cnt; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: };