Artifact 709c778ec7e505b9f285f572e7102dbd97ff5358:
0000: 23 69 6e 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 #include <vector
0010: 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 >.#include <stri
0020: 6e 67 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 73 73 ng>.#include <ss
0030: 74 72 65 61 6d 3e 0a 23 69 6e 63 6c 75 64 65 20 tream>.#include
0040: 3c 73 65 74 3e 0a 23 69 6e 63 6c 75 64 65 20 3c <set>.#include <
0050: 6d 61 70 3e 0a 75 73 69 6e 67 20 6e 61 6d 65 73 map>.using names
0060: 70 61 63 65 20 73 74 64 3b 0a 0a 73 74 72 75 63 pace std;..struc
0070: 74 20 50 65 6e 4c 69 66 74 0a 7b 0a 09 74 79 70 t PenLift.{..typ
0080: 65 64 65 66 20 70 61 69 72 3c 69 6e 74 2c 20 69 edef pair<int, i
0090: 6e 74 3e 20 20 20 20 20 20 20 20 20 20 20 70 6f nt> po
00a0: 69 6e 74 3b 0a 09 74 79 70 65 64 65 66 20 6d 61 int;..typedef ma
00b0: 70 3c 20 70 6f 69 6e 74 2c 20 73 65 74 3c 70 6f p< point, set<po
00c0: 69 6e 74 3e 20 3e 20 67 72 61 70 68 3b 0a 0a 09 int> > graph;...
00d0: 69 6e 74 20 6e 75 6d 54 69 6d 65 73 28 20 76 65 int numTimes( ve
00e0: 63 74 6f 72 3c 73 74 72 69 6e 67 3e 20 73 65 67 ctor<string> seg
00f0: 6d 65 6e 74 73 2c 20 69 6e 74 20 6e 20 29 0a 09 ments, int n )..
0100: 7b 0a 09 09 2f 2f 20 44 65 74 65 72 6d 69 6e 65 {...// Determine
0110: 20 41 6c 6c 20 53 69 67 6e 69 66 69 63 61 6e 74 All Significant
0120: 20 43 6f 6f 72 64 69 6e 61 74 65 73 0a 09 09 73 Coordinates...s
0130: 65 74 3c 69 6e 74 3e 20 78 73 2c 20 79 73 3b 0a et<int> xs, ys;.
0140: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
0150: 3c 73 65 67 6d 65 6e 74 73 2e 73 69 7a 65 28 29 <segments.size()
0160: 3b 20 2b 2b 69 29 0a 09 09 7b 0a 09 09 09 73 74 ; ++i)...{....st
0170: 72 69 6e 67 73 74 72 65 61 6d 20 73 69 6e 28 73 ringstream sin(s
0180: 65 67 6d 65 6e 74 73 5b 69 5d 29 3b 0a 09 09 09 egments[i]);....
0190: 69 6e 74 20 78 31 2c 20 79 31 2c 20 78 32 2c 20 int x1, y1, x2,
01a0: 79 32 3b 20 73 69 6e 20 3e 3e 20 78 31 20 3e 3e y2; sin >> x1 >>
01b0: 20 79 31 20 3e 3e 20 78 32 20 3e 3e 20 79 32 3b y1 >> x2 >> y2;
01c0: 0a 09 09 09 78 73 2e 69 6e 73 65 72 74 28 78 31 ....xs.insert(x1
01d0: 29 3b 0a 09 09 09 78 73 2e 69 6e 73 65 72 74 28 );....xs.insert(
01e0: 78 32 29 3b 0a 09 09 09 79 73 2e 69 6e 73 65 72 x2);....ys.inser
01f0: 74 28 79 31 29 3b 0a 09 09 09 79 73 2e 69 6e 73 t(y1);....ys.ins
0200: 65 72 74 28 79 32 29 3b 0a 09 09 7d 0a 0a 09 09 ert(y2);...}....
0210: 2f 2f 20 43 6f 6e 73 74 72 75 63 74 20 74 68 65 // Construct the
0220: 20 67 72 61 70 68 2c 20 73 65 70 61 72 61 74 65 graph, separate
0230: 64 20 62 79 20 61 6c 6c 20 73 69 67 6e 69 66 69 d by all signifi
0240: 63 61 6e 74 20 63 6f 6f 72 64 69 6e 61 74 65 73 cant coordinates
0250: 0a 09 09 67 72 61 70 68 20 47 3b 0a 09 09 66 6f ...graph G;...fo
0260: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 73 65 67 r(int i=0; i<seg
0270: 6d 65 6e 74 73 2e 73 69 7a 65 28 29 3b 20 2b 2b ments.size(); ++
0280: 69 29 0a 09 09 7b 0a 09 09 09 73 74 72 69 6e 67 i)...{....string
0290: 73 74 72 65 61 6d 20 73 69 6e 28 73 65 67 6d 65 stream sin(segme
02a0: 6e 74 73 5b 69 5d 29 3b 0a 09 09 09 69 6e 74 20 nts[i]);....int
02b0: 78 31 2c 20 79 31 2c 20 78 32 2c 20 79 32 3b 20 x1, y1, x2, y2;
02c0: 73 69 6e 20 3e 3e 20 78 31 20 3e 3e 20 79 31 20 sin >> x1 >> y1
02d0: 3e 3e 20 78 32 20 3e 3e 20 79 32 3b 0a 09 09 09 >> x2 >> y2;....
02e0: 69 66 28 20 78 31 20 3d 3d 20 78 32 20 29 0a 09 if( x1 == x2 )..
02f0: 09 09 7b 0a 09 09 09 09 73 65 74 3c 69 6e 74 3e ..{.....set<int>
0300: 3a 3a 69 74 65 72 61 74 6f 72 20 69 74 20 3d 20 ::iterator it =
0310: 79 73 2e 6c 6f 77 65 72 5f 62 6f 75 6e 64 28 6d ys.lower_bound(m
0320: 69 6e 28 79 31 2c 79 32 29 29 3b 0a 09 09 09 09 in(y1,y2));.....
0330: 73 65 74 3c 69 6e 74 3e 3a 3a 69 74 65 72 61 74 set<int>::iterat
0340: 6f 72 20 65 64 20 3d 20 79 73 2e 75 70 70 65 72 or ed = ys.upper
0350: 5f 62 6f 75 6e 64 28 6d 61 78 28 79 31 2c 79 32 _bound(max(y1,y2
0360: 29 29 3b 0a 09 09 09 09 66 6f 72 28 73 65 74 3c ));.....for(set<
0370: 69 6e 74 3e 3a 3a 69 74 65 72 61 74 6f 72 20 70 int>::iterator p
0380: 76 3d 69 74 2b 2b 3b 20 69 74 21 3d 65 64 3b 20 v=it++; it!=ed;
0390: 2b 2b 69 74 2c 2b 2b 70 76 29 0a 09 09 09 09 09 ++it,++pv)......
03a0: 47 5b 70 6f 69 6e 74 28 78 31 2c 2a 70 76 29 5d G[point(x1,*pv)]
03b0: 2e 69 6e 73 65 72 74 28 70 6f 69 6e 74 28 78 31 .insert(point(x1
03c0: 2c 2a 69 74 29 29 2c 0a 09 09 09 09 09 47 5b 70 ,*it)),......G[p
03d0: 6f 69 6e 74 28 78 31 2c 2a 69 74 29 5d 2e 69 6e oint(x1,*it)].in
03e0: 73 65 72 74 28 70 6f 69 6e 74 28 78 31 2c 2a 70 sert(point(x1,*p
03f0: 76 29 29 3b 0a 09 09 09 7d 0a 09 09 09 65 6c 73 v));....}....els
0400: 65 0a 09 09 09 7b 0a 09 09 09 09 73 65 74 3c 69 e....{.....set<i
0410: 6e 74 3e 3a 3a 69 74 65 72 61 74 6f 72 20 69 74 nt>::iterator it
0420: 20 3d 20 78 73 2e 6c 6f 77 65 72 5f 62 6f 75 6e = xs.lower_boun
0430: 64 28 6d 69 6e 28 78 31 2c 78 32 29 29 3b 0a 09 d(min(x1,x2));..
0440: 09 09 09 73 65 74 3c 69 6e 74 3e 3a 3a 69 74 65 ...set<int>::ite
0450: 72 61 74 6f 72 20 65 64 20 3d 20 78 73 2e 75 70 rator ed = xs.up
0460: 70 65 72 5f 62 6f 75 6e 64 28 6d 61 78 28 78 31 per_bound(max(x1
0470: 2c 78 32 29 29 3b 0a 09 09 09 09 66 6f 72 28 73 ,x2));.....for(s
0480: 65 74 3c 69 6e 74 3e 3a 3a 69 74 65 72 61 74 6f et<int>::iterato
0490: 72 20 70 76 3d 69 74 2b 2b 3b 20 69 74 21 3d 65 r pv=it++; it!=e
04a0: 64 3b 20 2b 2b 69 74 2c 2b 2b 70 76 29 0a 09 09 d; ++it,++pv)...
04b0: 09 09 09 47 5b 70 6f 69 6e 74 28 2a 70 76 2c 79 ...G[point(*pv,y
04c0: 31 29 5d 2e 69 6e 73 65 72 74 28 70 6f 69 6e 74 1)].insert(point
04d0: 28 2a 69 74 2c 79 31 29 29 2c 0a 09 09 09 09 09 (*it,y1)),......
04e0: 47 5b 70 6f 69 6e 74 28 2a 69 74 2c 79 31 29 5d G[point(*it,y1)]
04f0: 2e 69 6e 73 65 72 74 28 70 6f 69 6e 74 28 2a 70 .insert(point(*p
0500: 76 2c 79 31 29 29 3b 0a 09 09 09 7d 0a 09 09 7d v,y1));....}...}
0510: 0a 0a 09 09 2f 2f 20 63 6f 75 6e 74 20 74 68 65 ....// count the
0520: 20 6e 75 6d 62 65 72 20 6f 66 20 6f 64 64 20 76 number of odd v
0530: 65 72 74 69 63 65 73 20 28 2f 32 29 20 70 65 72 ertices (/2) per
0540: 20 63 6f 6e 6e 65 63 74 65 64 20 63 6f 6d 70 6f connected compo
0550: 6e 65 6e 74 73 0a 09 09 73 65 74 3c 70 6f 69 6e nents...set<poin
0560: 74 3e 20 76 69 73 3b 0a 0a 09 09 69 6e 74 20 63 t> vis;....int c
0570: 6e 74 20 3d 20 30 3b 0a 09 09 66 6f 72 28 67 72 nt = 0;...for(gr
0580: 61 70 68 3a 3a 69 74 65 72 61 74 6f 72 20 73 3d aph::iterator s=
0590: 47 2e 62 65 67 69 6e 28 29 3b 20 73 21 3d 47 2e G.begin(); s!=G.
05a0: 65 6e 64 28 29 3b 20 2b 2b 73 29 0a 09 09 09 69 end(); ++s)....i
05b0: 66 28 20 21 76 69 73 2e 63 6f 75 6e 74 28 73 2d f( !vis.count(s-
05c0: 3e 66 69 72 73 74 29 20 29 0a 09 09 09 09 63 6e >first) ).....cn
05d0: 74 20 2b 3d 20 6d 61 78 28 31 2c 20 6e 75 6d 4f t += max(1, numO
05e0: 64 64 28 73 2d 3e 66 69 72 73 74 2c 20 47 2c 20 dd(s->first, G,
05f0: 76 69 73 2c 20 6e 29 2f 32 29 3b 0a 09 09 72 65 vis, n)/2);...re
0600: 74 75 72 6e 20 63 6e 74 20 2d 20 31 3b 20 2f 2f turn cnt - 1; //
0610: 20 66 69 72 73 74 20 74 6f 75 63 68 20 64 6f 20 first touch do
0620: 6e 6f 74 20 72 65 71 75 69 72 65 20 61 20 70 65 not require a pe
0630: 6e 2d 6c 69 66 74 0a 09 7d 0a 0a 09 2f 2f 20 73 n-lift..}...// s
0640: 69 6d 70 6c 65 20 64 66 73 0a 09 69 6e 74 20 6e imple dfs..int n
0650: 75 6d 4f 64 64 28 20 70 6f 69 6e 74 20 70 2c 20 umOdd( point p,
0660: 67 72 61 70 68 26 20 47 2c 20 73 65 74 3c 70 6f graph& G, set<po
0670: 69 6e 74 3e 26 20 76 69 73 2c 20 69 6e 74 20 6e int>& vis, int n
0680: 20 29 0a 09 7b 0a 09 09 69 66 28 20 76 69 73 2e )..{...if( vis.
0690: 63 6f 75 6e 74 28 70 29 20 29 0a 09 09 09 72 65 count(p) )....re
06a0: 74 75 72 6e 20 30 3b 0a 09 09 76 69 73 2e 69 6e turn 0;...vis.in
06b0: 73 65 72 74 28 70 29 3b 0a 0a 09 09 69 6e 74 20 sert(p);....int
06c0: 63 6e 74 20 3d 20 47 5b 70 5d 2e 73 69 7a 65 28 cnt = G[p].size(
06d0: 29 2a 6e 20 25 20 32 3b 20 2f 2f 20 69 66 20 6f )*n % 2; // if o
06e0: 64 64 20 64 65 67 72 65 65 20 74 68 65 6e 20 31 dd degree then 1
06f0: 20 65 6c 73 65 20 30 0a 09 09 66 6f 72 28 73 65 else 0...for(se
0700: 74 3c 70 6f 69 6e 74 3e 3a 3a 69 74 65 72 61 74 t<point>::iterat
0710: 6f 72 20 69 74 3d 47 5b 70 5d 2e 62 65 67 69 6e or it=G[p].begin
0720: 28 29 3b 20 69 74 21 3d 47 5b 70 5d 2e 65 6e 64 (); it!=G[p].end
0730: 28 29 3b 20 2b 2b 69 74 29 0a 09 09 09 63 6e 74 (); ++it)....cnt
0740: 20 2b 3d 20 6e 75 6d 4f 64 64 28 2a 69 74 2c 20 += numOdd(*it,
0750: 47 2c 20 76 69 73 2c 20 6e 29 3b 0a 09 09 72 65 G, vis, n);...re
0760: 74 75 72 6e 20 63 6e 74 3b 0a 09 7d 0a 7d 3b 0a turn cnt;..}.};.