Artifact 709c778ec7e505b9f285f572e7102dbd97ff5358

• File SRM/144/1C.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <map>
using namespace std;

struct PenLift
{
	typedef pair<int, int>           point;
	typedef map< point, set<point> > graph;

	int numTimes( vector<string> segments, int n )
	{
		// Determine All Significant Coordinates
		set<int> xs, ys;
		for(int i=0; i<segments.size(); ++i)
		{
			stringstream sin(segments[i]);
			int x1, y1, x2, y2; sin >> x1 >> y1 >> x2 >> y2;
			xs.insert(x1);
			xs.insert(x2);
			ys.insert(y1);
			ys.insert(y2);
		}

		// Construct the graph, separated by all significant coordinates
		graph G;
		for(int i=0; i<segments.size(); ++i)
		{
			stringstream sin(segments[i]);
			int x1, y1, x2, y2; sin >> x1 >> y1 >> x2 >> y2;
			if( x1 == x2 )
			{
				set<int>::iterator it = ys.lower_bound(min(y1,y2));
				set<int>::iterator ed = ys.upper_bound(max(y1,y2));
				for(set<int>::iterator pv=it++; it!=ed; ++it,++pv)
					G[point(x1,*pv)].insert(point(x1,*it)),
					G[point(x1,*it)].insert(point(x1,*pv));
			}
			else
			{
				set<int>::iterator it = xs.lower_bound(min(x1,x2));
				set<int>::iterator ed = xs.upper_bound(max(x1,x2));
				for(set<int>::iterator pv=it++; it!=ed; ++it,++pv)
					G[point(*pv,y1)].insert(point(*it,y1)),
					G[point(*it,y1)].insert(point(*pv,y1));
			}
		}

		// count the number of odd vertices (/2) per connected components
		set<point> vis;

		int cnt = 0;
		for(graph::iterator s=G.begin(); s!=G.end(); ++s)
			if( !vis.count(s->first) )
				cnt += max(1, numOdd(s->first, G, vis, n)/2);
		return cnt - 1; // first touch do not require a pen-lift
	}

	// simple dfs
	int numOdd( point p, graph& G, set<point>& vis, int n )
	{
		if( vis.count(p) )
			return 0;
		vis.insert(p);

		int cnt = G[p].size()*n % 2; // if odd degree then 1 else 0
		for(set<point>::iterator it=G[p].begin(); it!=G[p].end(); ++it)
			cnt += numOdd(*it, G, vis, n);
		return cnt;
	}
};