Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _USE_MATH_DEFINES
- #include <iostream>
- #include <string>
- #include <map>
- #include <set>
- #include <algorithm>
- #include <vector>
- #include <stdio.h>
- #include <cmath>
- #include <math.h>
- #include <queue>
- #include <stack>
- #include <climits>
- #include <deque>
- #include <ctime>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef unsigned int ui;
- #define mh() make_heap()
- #define poph() pop_heap()
- #define pushh() push_heap()
- #define sor(n) n.begin(), n.end()
- #define rsor(n) n.rbegin(), n.rend()
- #define mp make_pair
- #define files freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout)
- #define p(T) pair<T,T>
- #define znac(l) abs(l)/l
- #define A(y1,y2) y1-y2
- #define B(x1,x2) x2-x1
- #define C(x1,y1,x2,y2) -y2*(x2-x1)-x2*(y1-y2)
- #define rs(x1,y1,x2,y2) sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))
- struct pt {
- double x, y;
- };
- struct line {
- double a, b, c;
- };
- const double EPS = 1e-9;
- double det(double a, double b, double c, double d) {
- return a * d - b * c;
- }
- bool intersect(line m, line n, pt & res) {
- double zn = det(m.a, m.b, n.a, n.b);
- if (abs(zn) < EPS)
- return false;
- res.x = -det(m.c, m.b, n.c, n.b) / zn;
- res.y = -det(m.a, m.c, n.a, n.c) / zn;
- return true;
- }
- bool parallel(line m, line n) {
- return abs(det(m.a, m.b, n.a, n.b)) < EPS;
- }
- bool equivalent(line m, line n) {
- return abs(det(m.a, m.b, n.a, n.b)) < EPS
- && abs(det(m.a, m.c, n.a, n.c)) < EPS
- && abs(det(m.b, m.c, n.b, n.c)) < EPS;
- }
- double MIN(p(double)fr, p(double)sc, p(double)t)
- {
- line frst = { A(fr.second,sc.second),B(fr.first,sc.first),C(fr.first,fr.second,sc.first,sc.second) };
- line sec = {-frst.b,frst.a,frst.b*t.first-frst.a*t.second };
- if (!parallel(frst, sec) && !equivalent(frst, sec))
- {
- pt res;
- intersect(frst, sec, res);
- double l = rs(fr.first, fr.second, sc.first, sc.second);
- double ll = rs(fr.first, fr.second, res.x, res.y);
- double lr = rs(res.x, res.y, sc.first, sc.second);
- if (abs(l-(ll + lr)) > EPS)
- {
- return min(rs(fr.first, fr.second, t.first, t.second), rs(t.first, t.second, sc.first, sc.second));
- }
- else
- {
- double H = abs((frst.a*t.first +frst.b*t.second + frst.c) / sqrt(frst.a*frst.a + frst.b*frst.b));
- return min(H, min(rs(fr.first, fr.second, t.first, t.second), rs(t.first, t.second, sc.first, sc.second)));
- }
- }
- else
- {
- return min(rs(fr.first, fr.second, t.first, t.second), rs(t.first, t.second, sc.first, sc.second));
- }
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- files;
- #endif
- p(double) t;
- ll n;
- cin >> t.first >> t.second>>n;
- vector<p(double)>cord(n + 1);
- for (int i = 1; i <= n; i++)
- {
- cin >> cord[i].first >> cord[i].second;
- }
- ll last = 0;
- bool good = 1;
- for (int i = 1; i <= n; i++)
- {
- double ras;
- line frst;
- if (i == 1)
- {
- frst = { A(cord[i].second,cord[n].second),B(cord[i].first,cord[n].first),C(cord[i].first,cord[i].second,cord[n].first,cord[n].second) };
- }
- else
- frst = { A(cord[i].second,cord[i-1].second),B(cord[i].first,cord[i-1].first),C(cord[i].first,cord[i].second,cord[i-1].first,cord[i-1].second) };
- double H = (frst.a*t.first + frst.b*t.second + frst.c) / sqrt(frst.a*frst.a + frst.b*frst.b);
- if (last == 0)
- {
- last = znac(H);
- }
- else
- {
- if (abs(H) < EPS)
- {
- }
- else
- if (last != znac(H))
- {
- good = 0;
- break;
- }
- }
- }
- if (good)
- {
- printf("%.3lf", 0.0);
- return 0;
- }
- double answ = INT_MAX;
- for (int i = 1; i <= n; i++)
- {
- double ras;
- if (i == 1)
- {
- ras = MIN(cord[i], cord[n], t);
- }
- else
- {
- ras = MIN(cord[i], cord[i-1], t);
- }
- answ = min(answ, ras);
- }
- printf("%.3lf", 2*answ);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement