fork(5) download
copy 
  1. //
  2. //  main.cpp
  3. //  10263 - Railway
  4. //
  5. //  Created by Repon Macbook on 1/1/15.
  6. //  Copyright (c) 2015 Repon Macbook. All rights reserved.
  7. //
  8.  
  9. #include<iostream>
  10. #include<cstdio>
  11. #include<cmath>
  12. #include<cstring>
  13. #include<vector>
  14. #include<queue>
  15. #include<stack>
  16. #include<cstdlib>
  17. #include<algorithm>
  18. #include<set>
  19. #include<iterator>
  20. #include<cassert>
  21. #include <sstream>
  22. #include <climits>
  23. #include <list>
  24. #include <string>
  25. #include <map>
  26. using namespace std;
  27.  
  28. /*------- Constants---- */
  29. #define MX                      31650
  30. #define ll                      long long
  31. #define ull                     unsigned long long
  32. #define mod                     1000000007
  33. #define MEMSET_INF              63
  34. #define MEM_VAL                 1061109567
  35. #define FOR(i,n)                for( int i=0 ; i < n ; i++ )
  36. #define mp(i,j)                 make_pair(i,j)
  37. #define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
  38. #define pb(a)                   push_back((a))
  39. #define gc                      getchar_unlocked
  40. #define EPS                     1e-7
  41. #define PI                      acos(-1)
  42. #define INF                     1LL<<30
  43.  
  44. struct Point  {
  45.         double x,y;
  46.         bool del;
  47.         Point(){}
  48.         void scan(){
  49.                 cin >> x >> y;
  50.         }
  51.         bool operator == (const Point & P) const {
  52.                 if( x == P.x && y == P.y ) return true;
  53.                 return false;
  54.         }
  55.         void set(double _x , double _y){x= _x ; y = _y;}
  56. };
  57.  
  58.  
  59. double TriArea2( Point a , Point b ,Point c)
  60. {
  61.         return (.5*(a.x*(b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) ));
  62. }
  63.  
  64.  
  65.  
  66.  
  67. // To find orientation of ordered triplet (p, q, r).
  68. // The function returns following values
  69. // 0 --> p, q and r are colinear
  70. // 1 --> Clockwise
  71. // 2 --> Counterclockwise
  72.  
  73.  
  74. int ccw ( Point p,Point q ,Point r)
  75. {
  76.  
  77.         double val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
  78.  
  79.  
  80.         if( fabs(val) < EPS) return 0;
  81.         if( val > EPS ) return  1;
  82.         else return 2 ;
  83.  
  84. }
  85.  
  86.  
  87. bool onSegment( Point p , Point q ,Point r)
  88. {
  89.         // Given three colinear points p, q, r, the function checks if
  90.         // point q lies on line segment 'pr'
  91.  
  92.         if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
  93.             q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
  94.                 return true;
  95.  
  96.         return false;
  97. }
  98.  
  99.  
  100. bool isIntersect( Point p1 , Point q1 , Point p2, Point q2)
  101. {
  102.  
  103.         int o1 = ccw(p1,q1,p2);
  104.         int o2 = ccw(p1,q1,q2);
  105.         int o3 = ccw(p2, q2, p1);
  106.         int o4 = ccw(p2, q2, q1);
  107.  
  108.         if(o1 != o2 && o3 !=o4) {
  109.                 return true;
  110.         }
  111.  
  112.         // p1, q1 and p2 are colinear and p2 lies on segment p1q1
  113.         if (o1 == 0 && onSegment(p1, p2, q1)) return true;
  114.  
  115.         // p1, q1 and p2 are colinear and q2 lies on segment p1q1
  116.         if (o2 == 0 && onSegment(p1, q2, q1)) return true;
  117.  
  118.         // p2, q2 and p1 are colinear and p1 lies on segment p2q2
  119.         if (o3 == 0 && onSegment(p2, p1, q2)) return true;
  120.  
  121.         // p2, q2 and q1 are colinear and q1 lies on segment p2q2
  122.         if (o4 == 0 && onSegment(p2, q1, q2)) return true;
  123.  
  124.         return false; // Doesn't fall in any of the above cases
  125.  
  126. }
  127.  
  128. bool isInside ( Point A , Point B, Point p)
  129. {
  130.         if( p.x >= min(A.x , B.x)  && p.x <= max(A.x ,B.x ) && p.y <= max(A.y , B.y )&& p.y >= min(A.y , B.y) ) return true;
  131.         return false;
  132. }
  133.  
  134. double slope ( Point a , Point b)
  135. {
  136.  
  137.  
  138.         if( fabs(a.x - b.x) < EPS){
  139.                 return INF;
  140.         }
  141.         else return (a.y - b.y) / (a.x - b.x ) + EPS;
  142. }
  143.  
  144.  
  145. struct Line  {
  146.  
  147.         double a,b,c;
  148.         double slop;
  149.         Line(){}
  150.         Line ( Point A , Point B)
  151.         {
  152.                 double sl = slope(A,B);
  153.  
  154.                 if( sl == INF) {
  155.                         a = 1;
  156.                         b = 0;
  157.                         c = - A.x;
  158.  
  159.                         if(fabs(c) < EPS) c = 0;
  160.  
  161.                 }
  162.                 else {
  163.                         a = -sl;
  164.                         b = 1;
  165.                         c = sl * A.x - A.y;
  166.                         if(fabs(c) < EPS) c = 0;
  167.                 }
  168.  
  169.         }
  170.         Line( double sl , Point A)
  171.         {
  172.                 if( sl == INF) {
  173.                         a = 1;
  174.                         b = 0;
  175.                         c = - A.x;
  176.  
  177.                         if(fabs(c) < EPS) c = 0;
  178.  
  179.                 }
  180.                 else {
  181.                         a = -sl;
  182.                         b = 1;
  183.                         c = sl * A.x - A.y;
  184.                         if(fabs(c) < EPS) c = 0;
  185.                 }
  186.         }
  187. };
  188.  
  189.  
  190. bool isParallel(Point a,Point b , Point c ,Point d)
  191. {
  192.         // Return if ab || cd
  193.  
  194.         if(fabs((a.x - b.x)*(c.y - d.y) - (a.y-b.y) *(c.x-d.x)) < EPS) return true;
  195.         return false;
  196.  
  197.  
  198. }
  199.  
  200.  
  201. Point intersectingPoint( Line &l1 , Line &l2)
  202. {
  203.  
  204.         // Return The (x,y) intersection of Two line L1 , L2
  205.  
  206.  
  207.         Point ret;
  208.         l1.c = - l1.c;
  209.         l2.c = -l2.c;
  210.         ret.x = (l1.c * l2.b - l2.c * l1.b) / ( l1.a * l2.b - l1.b *l2.a);
  211.         ret.y = (l1.a * l2.c - l2.a * l1.c) / ( l1.a *l2.b - l1.b *l2.a);
  212.  
  213.         if(fabs(ret.x) < EPS ) ret.x = 0.0;
  214.         if(fabs(ret.y) < EPS ) ret.y = 0.0;
  215.         return ret;
  216. }
  217.  
  218. double Dist (Point a, Point b)
  219. {
  220.         // Return distance between Point a , point b
  221.         return sqrt((a.x - b.x) *( a.x - b.x) + ( a.y - b.y) *(a.y - b.y)) + EPS;
  222. }
  223.  
  224.  
  225. int main()
  226. {
  227.  
  228.  
  229.         Point M , tmp ;
  230.         int N ;
  231.         double a, b ;
  232.         while (scanf("%lf %lf",&a,&b)==2 ) {
  233.                 M.set(a,b);
  234.                 cin >> N ;
  235.                 Point pv;
  236.  
  237.                 double min_dst = INF;
  238.                 Point ans;
  239.                 for( int i = 0 ;i <= N ; i ++ ){
  240.                         cin >> a >> b;
  241.                         tmp.set(a, b);
  242.                         if( i >= 1){
  243.  
  244.                                 double ss  = slope(pv, tmp);
  245.                                 if( ss == INF){
  246.                                         ss = 0;
  247.                                 }
  248.                                 else if( ss == 0){
  249.                                         ss = INF;
  250.                                 }
  251.  
  252.                                 else ss = -1./ss;
  253.  
  254.                                 Line L(ss , M);
  255.                                 Line AB ( tmp,pv);
  256.                                 Point ins  = intersectingPoint(L, AB);
  257.  
  258.                                 if(onSegment(tmp , ins, pv)){
  259.                                         double d = Dist(ins, M);
  260.                                         if(d < min_dst - EPS ){
  261.                                                 min_dst = d;
  262.                                                 ans = ins;
  263.                                         }
  264.                                 }
  265.                                 else {
  266.                                         double dm =Dist(M, tmp);
  267.                                         double dmm = Dist(M, pv);
  268.                                         if( dm < min_dst - EPS ){
  269.                                                 min_dst = dm;
  270.                                                 ans = tmp;
  271.                                         }
  272.                                         if( dmm < min_dst - EPS ){
  273.                                                 min_dst = dmm;
  274.                                                 ans = pv;
  275.                                         }
  276.  
  277.                                 }
  278.  
  279.  
  280.  
  281.                         }
  282.                       pv = tmp;
  283.                 }
  284.  
  285.                 printf("%.4lf\n%.4lf\n",ans.x ,ans.y );
  286.         }
  287.         return 0;
  288.  
  289. }
  290.  
  291.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
6
-3
3
0
1
5
5
9
-5
15
3
0
0
1
1
0
2
0
1
1
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
4
4
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
0
0
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
0.5
0.5
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
-0.5
-0.5
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
-2
-2
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
1
-1
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
2
-2
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
2.7654
2.3456
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
-1
-1
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
-2
-2
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
-3
-3
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
stdout
copy 
7.8966
-2.2414
1.0000
0.0000
0.0000
2.0000
3.0000
2.0000
-1.2000
0.6000
-0.5000
1.5000
-1.5000
0.0000
-1.0000
-2.0000
1.1000
-1.3000
1.7000
-1.1000
2.6741
2.1630
-1.8000
-0.6000
-1.0000
-2.0000
-1.0000
-2.0000
https://ideone.com/VoYlSF
language:
C++ (gcc 8.3)
created:
9 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!