equal
deleted
inserted
replaced
63 |
63 |
64 |
64 |
65 double totalLen(){ |
65 double totalLen(){ |
66 double tlen=0; |
66 double tlen=0; |
67 for(EdgeIt e(g);e!=INVALID;++e) |
67 for(EdgeIt e(g);e!=INVALID;++e) |
68 tlen+=sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare()); |
68 tlen+=std::sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare()); |
69 return tlen; |
69 return tlen; |
70 } |
70 } |
71 |
71 |
72 int tsp_impr_num=0; |
72 int tsp_impr_num=0; |
73 |
73 |
186 |
186 |
187 double f = (p.x * p.x + p.y * p.y) * (q.x * r.y - r.x * q.y) + |
187 double f = (p.x * p.x + p.y * p.y) * (q.x * r.y - r.x * q.y) + |
188 (q.x * q.x + q.y * q.y) * (r.x * p.y - p.x * r.y) + |
188 (q.x * q.x + q.y * q.y) * (r.x * p.y - p.x * r.y) + |
189 (r.x * r.x + r.y * r.y) * (p.x * q.y - q.x * p.y); |
189 (r.x * r.x + r.y * r.y) * (p.x * q.y - q.x * p.y); |
190 |
190 |
191 return d / (2 * a) + sqrt((d * d + e * e) / (4 * a * a) + f / a); |
191 return d / (2 * a) + std::sqrt((d * d + e * e) / (4 * a * a) + f / a); |
192 } |
192 } |
193 |
193 |
194 inline bool circle_form(const Point& p, const Point& q, const Point& r) { |
194 inline bool circle_form(const Point& p, const Point& q, const Point& r) { |
195 return rot90(q - p) * (r - q) < 0.0; |
195 return rot90(q - p) * (r - q) < 0.0; |
196 } |
196 } |
204 if (sx < q.x + epsilon) return q.y; |
204 if (sx < q.x + epsilon) return q.y; |
205 |
205 |
206 double a = q.x - p.x; |
206 double a = q.x - p.x; |
207 double b = (q.x - sx) * p.y - (p.x - sx) * q.y; |
207 double b = (q.x - sx) * p.y - (p.x - sx) * q.y; |
208 double d = (q.x - sx) * (p.x - sx) * (p - q).normSquare(); |
208 double d = (q.x - sx) * (p.x - sx) * (p - q).normSquare(); |
209 return (b - sqrt(d)) / a; |
209 return (b - std::sqrt(d)) / a; |
210 } |
210 } |
211 |
211 |
212 struct YLess { |
212 struct YLess { |
213 |
213 |
214 |
214 |
811 |
811 |
812 std::cout << "Number of nodes : " << countNodes(g) << std::endl; |
812 std::cout << "Number of nodes : " << countNodes(g) << std::endl; |
813 std::cout << "Number of arcs : " << countEdges(g) << std::endl; |
813 std::cout << "Number of arcs : " << countEdges(g) << std::endl; |
814 double tlen=0; |
814 double tlen=0; |
815 for(EdgeIt e(g);e!=INVALID;++e) |
815 for(EdgeIt e(g);e!=INVALID;++e) |
816 tlen+=sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare()); |
816 tlen+=std::sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare()); |
817 std::cout << "Total arc length : " << tlen << std::endl; |
817 std::cout << "Total arc length : " << tlen << std::endl; |
818 |
818 |
819 if(ap["eps"]) |
819 if(ap["eps"]) |
820 graphToEps(g,prefix+".eps").scaleToA4(). |
820 graphToEps(g,prefix+".eps").scaleToA4(). |
821 scale(600).nodeScale(.005).arcWidthScale(.001).preScale(false). |
821 scale(600).nodeScale(.005).arcWidthScale(.001).preScale(false). |