Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iomanip>
- #include <iostream>
- #include <vector>
- #include <complex>
- #include <cmath>
- using namespace std;
- typedef long double ld;
- typedef complex<ld> pt;
- const ld INF = 1e12, EPS = 1e-9;
- inline ld cp(const pt &a, const pt &b) { return a.real()*b.imag() - b.real()*a.imag();}
- inline ld sgn(const ld& x) { return abs(x) < EPS ? 0 : x/abs(x); }
- inline bool cmp_lex(const pt& a, const pt& b)
- { return a.real() < b.real() || (a.real() == b.real() && a.imag() < b.imag()); }
- // SIGNED distance. Pt on the right of vector (a -> b) will be NEGATIVE.
- inline ld lp_dist(const pt &a, const pt &b, const pt &p){
- return cp(b - a, p - a) / abs(b - a); }
- // flips point p across vector a->b
- inline pt flip(const pt& p, const pt& a, const pt& b) {
- ld d = lp_dist(a, b, p);
- return p-2*d*(b-a)*pt(0,1)/abs(b-a); }
- // handles ALL cases, change occurrences of <= to < to exclude endpoints
- bool seg_x_seg(pt a1, pt a2, pt b1, pt b2){
- //if (a1==a2 || b1==b2) return false; // uncomment to exclude endpoints
- int s1 = sgn(cp(a2 - a1, b1 - a1)), s2 = sgn(cp(a2 - a1, b2 - a1));
- int s3 = sgn(cp(b2 - b1, a1 - b1)), s4 = sgn(cp(b2 - b1, a2 - b1));
- if(!s1 && !s2 && !s3) { // collinear
- if (cmp_lex(a2, a1)) swap(a1,a2); if (cmp_lex(b2, b1)) swap(b1, b2);
- return !cmp_lex(b2, a1) && !cmp_lex(a2, b1);
- //return cmp_lex(a1, b2) && cmp_lex(b1, a2);//uncomment to exclude endpoints
- } return s1*s2 <= 0 && s3*s4 <= 0; }
- int main() {
- int N; int zz=1;
- while(cin >> N) {
- vector<pt> v;
- int px, py; cin >> px >> py;
- for (int i=0; i < N; i++) {
- int x, y; cin >> x >> y;
- v.push_back(pt(x, y));
- }
- ld res = INF;
- ld dp[N+3];
- for (int cnt=0; cnt < N; cnt++) {
- v.push_back(v.front());
- v.insert(v.begin(), pt(px, py));
- v.push_back(pt(px, py));
- vector<pt> v2(v.begin(), v.end());
- for (int i=0; i < N+2; i++)
- for (int j=i+1; j <= N+2; j++)
- v2[j] = flip(v2[j], v2[i], v2[i+1]);
- dp[0] = 0;
- for (int i=1; i <= N+2; i++) {
- dp[i] = INF;
- for (int j=0; j < i; j++) {
- if (dp[j] + abs(v2[j]-v2[i]) < dp[i]) {
- bool good = true;
- for (int k=j; k+1 <= i; k++)
- good &= seg_x_seg(v2[j], v2[i], v2[k], v2[k+1]);
- if (good) dp[i] = dp[j] + abs(v2[j]-v2[i]);
- }
- }
- }
- res = min(res, dp[N+2]);
- v.pop_back();
- v.erase(v.begin());
- v.erase(v.begin());
- }
- cout << "Case " << zz++ << ": " << fixed << setprecision(2) << res << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement