Solution to SRM144 Penlift

PenLift.cxx

#include <sstream>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <set>
#include <list>
#include "graphs.h"
#include "line.h"
using namespace std;

class PenLift{

  vector<Line> m_inLines;
  set<Point> m_points; 
  Graph<Point> m_graph;
  
public: 
 
  static Line getLine(const string& szPoints){ return Line(szPoints);}
  int  numTimes(vector<string>, int);
  void mergeLines();  
  void intersectLines();
  void splitLines(const Point& point);
  void createGraph();
};


void PenLift::createGraph(){
  for(vector<Line>::iterator it = m_inLines.begin() ; it != m_inLines.end() ; ++it)
    m_graph.insertEdge(it->getStart(), it->getEnd());
}

void PenLift::splitLines(const Point& point)
{
  for(int i = 0; i < m_inLines.size() ; i++) 
    if(point != m_inLines[i].getStart() && point != m_inLines[i].getEnd() && m_inLines[i].isPointOnSegment(point)){
      m_inLines.push_back (Line(point, m_inLines[i].getEnd()) );
      m_inLines[i] = Line(point, m_inLines[i].getStart());
    }
}

void PenLift::intersectLines(){ 
  for(int i  = 0; i < m_inLines.size(); ++i )
    for(int j = i+1; j < m_inLines.size(); ++j)
      {
	Point newPoint;
	if(m_inLines[i].intersection(m_inLines[j], newPoint))
	  m_points.insert(Point(newPoint));
      }
  
  for(set<Point>::iterator it = m_points.begin() ; it != m_points.end() ; ++it)
    splitLines(*it);
}

void PenLift::mergeLines(){ 
  for(int i  = 0; i < m_inLines.size(); ++i )
    for(int j = i+1; j < m_inLines.size(); ++j)
      if(m_inLines[i].merge(m_inLines[j], m_inLines[i]))
	{
	  m_inLines.erase(m_inLines.begin() + j);
	  i--;
	  break;
	}
}

int PenLift::numTimes(vector<string> segments, int n) 
{
            
  transform(segments.begin(), segments.end(), back_inserter(m_inLines), PenLift::getLine);
  mergeLines();    
  intersectLines();
  createGraph();  
  vector< Graph<Point> > g = m_graph.getConnectedGraphs();

  if(n % 2 == 0)
    return (g.size() - 1);

  int rValue =0;
  for( vector< Graph<Point> >::iterator it = g.begin() ; it != g.end(); ++it)
    {
      int odd = it->numOddVertices()/2;
      rValue +=  odd > 0 ? odd:1;	
    }
  return rValue - 1;
}



int main(){

  vector<string> s;
  string test[] = {"0 0 1 0",   "2 0 4 0",   "5 0 8 0",   "9 0 13 0",
		   "0 1 1 1",   "2 1 4 1",   "5 1 8 1",   "9 1 13 1",
		   "0 0 0 1",   "1 0 1 1",   "2 0 2 1",   "3 0 3 1",
		   "4 0 4 1",   "5 0 5 1",   "6 0 6 1",   "7 0 7 1",
		   "8 0 8 1",   "9 0 9 1",   "10 0 10 1", "11 0 11 1",
		   "12 0 12 1", "13 0 13 1"};

  string test2[]= {"-2 6 -2 1",  "2 6 2 1",  "6 -2 1 -2",  "6 2 1 2",
		   "-2 5 -2 -1", "2 5 2 -1", "5 -2 -1 -2", "5 2 -1 2",
		   "-2 1 -2 -5", "2 1 2 -5", "1 -2 -5 -2", "1 2 -5 2",
		   "-2 -1 -2 -6","2 -1 2 -6","-1 -2 -6 -2","-1 2 -6 2"};

  string test3[] = {"-252927 -1000000 -252927 549481","628981 580961 -971965 580961",
		    "159038 -171934 159038 -420875","159038 923907 159038 418077",
		    "1000000 1000000 -909294 1000000","1000000 -420875 1000000 66849",
		    "1000000 -171934 628981 -171934","411096 66849 411096 -420875",
		    "-1000000 -420875 -396104 -420875","1000000 1000000 159038 1000000",
		    "411096 66849 411096 521448","-971965 580961 -909294 580961",
		    "159038 66849 159038 -1000000","-971965 1000000 725240 1000000",
		    "-396104 -420875 -396104 -171934","-909294 521448 628981 521448",
		    "-909294 1000000 -909294 -1000000","628981 1000000 -909294 1000000",
		    "628981 418077 -396104 418077","-971965 -420875 159038 -420875",
		    "1000000 -1000000 -396104 -1000000","-971965 66849 159038 66849",
		    "-909294 418077 1000000 418077","-909294 418077 411096 418077",
		    "725240 521448 725240 418077","-252927 -1000000 -1000000 -1000000",
		    "411096 549481 -1000000 549481","628981 -171934 628981 923907",
		    "-1000000 66849 -1000000 521448","-396104 66849 -396104 1000000",
		    "628981 -1000000 628981 521448","-971965 521448 -396104 521448",
		    "-1000000 418077 1000000 418077","-1000000 521448 -252927 521448",
		    "725240 -420875 725240 -1000000","-1000000 549481 -1000000 -420875",
		    "159038 521448 -396104 521448","-1000000 521448 -252927 521448",
		    "628981 580961 628981 549481","628981 -1000000 628981 521448",
		    "1000000 66849 1000000 -171934","-396104 66849 159038 66849",
		    "1000000 66849 -396104 66849","628981 1000000 628981 521448",
		    "-252927 923907 -252927 580961","1000000 549481 -971965 549481",
		    "-909294 66849 628981 66849","-252927 418077 628981 418077",
		    "159038 -171934 -909294 -171934","-252927 549481 159038 549481"};

  string test4[] = {"-883 -382 -883 685", "57 692 57 338", "-24 271 388 271", "-718 255 -718 -562", "-491 -167 -491 -528",
		    "980 -207 980 937", "267 939 267 4", "-266 -499 -266 126", "945 57 -66 57", "141 320 385 320",
		    "261 -852 261 -374", "-51 999 -98 999", "-848 -475 -848 -309", "123 73 -589 73", "151 -843 151 -341",
		    "-580 307 -580 31", "-115 -596 -115 230", "-545 534 -545 116", "-664 43 -664 -927", "162 -236 162 574",
		    "-697 -321 -697 -581", "436 -579 -912 -579", "-504 -787 -504 -258", "195 -11 -217 -11", "726 611 93 611",
		    "-528 572 -51 572", "151 559 727 559", "-585 -703 -585 -678", "-819 -516 -164 -516", "-609 -803 138 -803",
		    "-583 121 -583 822", "-934 839 -670 839", "302 341 302 -978", "425 751 425 -821", "-576 557 70 557",
		    "-334 -749 -282 -749", "463 -712 463 -761", "-979 900 -434 900", "-561 -227 883 -227", "275 68 275 96",
		    "871 500 601 500", "-585 -523 -585 284"};
 
 
  string test5[] = {"-360 672 -172 672", "-336 -930 -961 -930", "688 4 688 -967", "689 -237 -701 -237", "100 -867 100 -578",
		    "-758 889 -272 889", "-136 -314 -876 -314", "-901 -640 35 -640", "980 -639 -364 -639", "156 45 610 45",
		    "-245 569 -245 39", "850 40 -215 40", "-687 596 -687 -660", "-509 666 -509 457", "625 -309 372 -309",
		    "-582 -785 836 -785","-914 131 -914 58", "903 -339 903 -738", "-318 709 -318 71", "-635 742 -635 6",
		    "-49 246 -49 917", "694 -27 -355 -27", "-931 390 143 390", "40 -132 40 319", "346 637 643 637",
		    "945 952 573 952", "-102 898 -102 766", "979 615 979 113", "-761 465 -761 995", "10 398 -182 398",
		    "907 -688 907 -222", "-307 909 -307 966", "331 -520 -525 -520", "132 267 -530 267", "-237 -93 -237 -932",
		    "907 -685 653 -685", "796 501 796 -419", "663 -471 663 155", "23 388 23 -592", "44 401 -478 401",
		    "-335 -89 -755 -89", "99 -437 -475 -437", "486 5 486 -195", "381 -954 -521 -954", "-957 -909 -957 260",
		    "663 -264 663 -582", "219 954 -868 954"};

  string test6[] = {"-956 824 -745 824", "-637 -184 -637 -380", "-159 792 70 792", "344 367 -847 367",
		    "-239 640 -239 621", "468 -490 -785 -490", "-929 40 -131 40", "179 347 179 -764", 
		    "908 -688 908 -92", "292 -430 350 -430", "-583 840 -583 231", "-132 792 -781 792", 
		    "-262 -683 -262 -762", "893 -178 893 480", "375 158 375 502", "696 101 696 -228", 
		    "-51 -229 -51 659", "42 123 -517 123", "690 834 690 977", "827 152 827 388",
		    "-801 -555 -801 -194", "115 -61 115 -57", "553 -920 528 -920", "719 306 452 306",
		    "778 -280 -244 -280", "744 212 744 -120", "98 -856 -476 -856", "519 -276 519 -262",
		    "-614 -499 -614 35", "-20 95 511 95", "543 623 543 -286", "933 -390 -793 -390", 
		    "-898 -461 -898 -319"};    

  string test7[] = {"9 5 -7 5", "5 1 5 9"};
 
  for(int i = 0 ; i < 50 ;i++)
    {
      s.push_back(test3[i]);
    }
 
  PenLift t;
  cout<<"Ans: "<< t.numTimes(s, 9989091)<<endl;
 
}