fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define all(x) begin(x),end(x)
  4. template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  5. template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
  6. #define debug(a) cerr << "(" << #a << ": " << a << ")\n";
  7. typedef long long ll;
  8. typedef vector<int> vi;
  9. typedef vector<vi> vvi;
  10. typedef pair<int,int> pi;
  11. const int mxN = 500+1;
  12. const double oo = 1e20;
  13.  
  14. typedef complex<int> pt;
  15. #define X real()
  16. #define Y imag()
  17. auto cross(pt u, pt v) {return (ll)u.X*v.Y-(ll)u.Y*v.X;}
  18. auto sgn(ll a) {return a==0?0:(a>0?1:-1);}
  19. auto ccw(pt p1, pt p2, pt p3) {auto u = p2-p1, v = p3-p2;return cross(u,v);}
  20. auto in(pt p1, pt p2) {return (ll)p1.X*p2.X+(ll)p1.Y*p2.Y;}
  21. auto norm(pt p) {return (ll)p.X*p.X+(ll)p.Y*p.Y;}
  22. bool comp(const pt& a, const pt& b) { return a.X<b.X or (a.X==b.X and a.Y < b.Y);}
  23. void read(pt& p) {
  24.     int a,b; cin >> a >> b;
  25.     p = {a,b};
  26. }
  27. double dist[mxN][mxN];
  28. void solve() {
  29.     int n; cin >> n;
  30.     vector<pt> pts(n);
  31.     for(auto& i : pts) read(i);
  32.     pt b; read(b);
  33.     for(int i=0;i<n;++i) fill(dist[i],dist[i]+n,oo);
  34.     for(int i=0;i<n;++i) {
  35.         for(int j=0;j<n;++j) {
  36.             if(ccw(pts[i],pts[j],b)>0) {
  37.                 dist[i][j] = sqrt(norm(pts[i]-pts[j]));
  38.             }
  39.         }
  40.     }
  41.     for(int j=0;j<n;++j) for(int i=0;i<n;++i) for(int k=0;k<n;++k) {
  42.         dist[i][k] = min(dist[i][k], dist[i][j]+dist[j][k]);
  43.     }
  44.     double ans = oo;
  45.     for(int i=0;i<n;++i) ans=min(ans,dist[i][i]);
  46.     if(ans!=oo) cout << setprecision(15) << ans << '\n';
  47.     else cout << "IMPOSSIBLE\n";
  48. }
  49. int main() {
  50.     ios_base::sync_with_stdio(false);
  51.     cin.tie(NULL);
  52.     int T; cin >> T;
  53.     for(int i=1;i<=T;++i) {
  54.         cout << "Case #" << i << ": ";
  55.         solve();
  56.     }
  57. }
Success #stdin #stdout 0.01s 5652KB
comments (?)
stdin
copy 
2
2
0 0
5 0
2 2
3
0 0
5 0
0 5
1 1
stdout
copy 
Case #1: IMPOSSIBLE
Case #2: 17.0710678118655
https://ideone.com/u9pam3
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!