API tools faq
paste
Advertisement
anoosykh95

Untitled

anoosykh95
Jul 22nd, 2016
436
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.02 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef complex<long double> point;
  5. #define sz(a) ((int)(a).size())
  6. #define all(n) (n).begin(),(n).end()
  7. #define EPS 1e-9
  8. #define OO 1e9
  9. #define X real()
  10. #define Y imag()
  11. #define vec(a,b) ((b)-(a))
  12. #define polar(r,t) ((r)*exp(point(0,(t))))
  13. #define angle(v) (atan2((v).Y,(v).X))
  14. #define length(v) ((long double)hypot((v).Y,(v).X))
  15. #define lengthSqr(v) (dot(v,v))
  16. #define dot(a,b) ((conj(a)*(b)).real())
  17. #define cross(a,b) ((conj(a)*(b)).imag())
  18. #define rotate(v,t) (polar(v,t))
  19. #define rotateabout(v,t,a)  (rotate(vec(a,v),t)+(a))
  20. #define reflect(p,m) ((conj((p)/(m)))*(m))
  21. #define normalize(p) ((p)/length(p))
  22. #define same(a,b) (lengthSqr(vec(a,b))<EPS)
  23. #define mid(a,b) (((a)+(b))/point(2,0))
  24. #define perp(a) (point(-(a).Y,(a).X))
  25. #define colliner pointOnLine
  26.  
  27. enum STATE {
  28.         IN, OUT, BOUNDRY
  29. };
  30.  
  31. bool intersect(const point &a, const point &b, const point &p, const point &q,
  32.               point &ret) {
  33.  
  34.     //handle degenerate cases (2 parallel lines, 2 identical lines,   line is 1 point)
  35.  
  36.     double d1 = cross(p - a, b - a);
  37.     double d2 = cross(q - a, b - a);
  38.     ret = (point(d1,0) * q - point(d2,0) * p) / point(d1 - d2,0);
  39.     if(fabs(d1 - d2) > EPS) return 1;
  40.     return 0;
  41. }
  42.  
  43. bool pointOnLine(const point& a, const point& b, const point& p) {
  44.     // degenerate case: line is a point
  45.     return fabs(cross(vec(a,b),vec(a,p))) < EPS;
  46. }
  47.  
  48. bool pointOnRay(const point& a, const point& b, const point& p) {
  49.     //IMP NOTE: a,b,p must be collinear
  50.     return dot(vec(a,p), vec(a,b)) > -EPS;
  51. }
  52.  
  53. bool pointOnSegment(const point& a, const point& b, const point& p) {
  54.     if(!colliner(a,b,p)) return 0;
  55.     return pointOnRay(a, b, p) && pointOnRay(b, a, p);
  56. }
  57.  
  58. long double pointLineDist(const point& a, const point& b, const point& p) {
  59.         // handle degenrate case: (a,b) is point
  60.  
  61.         return fabs(cross(vec(a,b),vec(a,p)) / length(vec(a,b)));
  62. }
  63.  
  64. long double pointSegmentDist(const point& a, const point& b, const point& p) {
  65.         if (dot(vec(a,b),vec(a,p)) < EPS)
  66.                 return length(vec(a,p));
  67.         if (dot(vec(b,a),vec(b,p)) < EPS)
  68.                 return length(vec(b,p));
  69.         return pointLineDist(a, b, p);
  70. }
  71.  
  72. int segmentLatticePointsCount(int x1, int y1, int x2, int y2) {
  73.         return abs(__gcd(x1 - x2, y1 - y2)) + 1;
  74. }
  75.  
  76. long double triangleAreaBH(long double b, long double h) {
  77.         return b * h / 2;
  78. }
  79.  
  80. long double triangleArea2sidesAngle(long double a, long double b, long double t) {
  81.         return fabs(a * b * sin(t) / 2);
  82. }
  83.  
  84. long double triangleArea2anglesSide(long double t1, long double t2,
  85.                 long double s) {
  86.         return fabs(s * s * sin(t1) * sin(t2) / (2 * sin(t1 + t2)));
  87. }
  88.  
  89. long double triangleArea3sides(long double a, long double b, long double c) {
  90.         long double s((a + b + c) / 2);
  91.         return sqrt(s * (s - a) * (s - b) * (s - c));
  92. }
  93.  
  94. long double triangleArea3points(const point& a, const point& b, const point& c) {
  95.         return fabs(cross(a,b) + cross(b,c) + cross(c,a)) / 2;
  96. }
  97.  
  98. //count interior
  99. int picksTheorm(int a, int b) {
  100.         return a - b / 2 + 1;
  101. }
  102.  
  103. //get angle opposite to side a
  104. long double cosRule(long double a, long double b, long double c) {
  105.         // Handle denom = 0
  106.         long double res = (b * b + c * c - a * a) / (2 * b * c);
  107.         if (res > 1)
  108.                 res = 1;
  109.         if (res < -1)
  110.                 res = -1;
  111.         return acos(res);
  112. }
  113.  
  114. long double sinRuleAngle(long double s1, long double s2, long double a1) {
  115.         // Handle denom = 0
  116.         long double res = s2 * sin(a1) / s1;
  117.         if (res > 1)
  118.                 res = 1;
  119.         if (res < -1)
  120.                 res = -1;
  121.         return asin(res);
  122. }
  123.  
  124. long double sinRuleSide(long double s1, long double a1, long double a2) {
  125.         // Handle denom = 0
  126.         long double res = s1 * sin(a2) / sin(a1);
  127.         return fabs(res);
  128. }
  129.  
  130. int circleLineIntersection(const point& p0, const point& p1, const point& cen,
  131.                 long double rad, point& r1, point & r2) {
  132.  
  133.         // handle degenerate case if p0 == p1
  134.         long double a, b, c, t1, t2;
  135.         a = dot(p1-p0,p1-p0);
  136.         b = 2 * dot(p1-p0,p0-cen);
  137.         c = dot(p0-cen,p0-cen) - rad * rad;
  138.         double det = b * b - 4 * a * c;
  139.         int res;
  140.         if (fabs(det) < EPS)
  141.                 det = 0, res = 1;
  142.         else if (det < 0)
  143.                 res = 0;
  144.         else
  145.                 res = 2;
  146.         det = sqrt(det);
  147.         t1 = (-b + det) / (2 * a);
  148.         t2 = (-b - det) / (2 * a);
  149.         r1 = p0 + t1 * (p1 - p0);
  150.         r2 = p0 + t2 * (p1 - p0);
  151.         return res;
  152. }
  153.  
  154. int circleCircleIntersection(const point &c1, const long double&r1,
  155.                 const point &c2, const long double&r2, point &res1, point &res2) {
  156.         if (same(c1,c2) && fabs(r1 - r2) < EPS) {
  157.                 res1 = res2 = c1;
  158.                 return fabs(r1) < EPS ? 1 : OO;
  159.         }
  160.         long double len = length(vec(c1,c2));
  161.         if (fabs(len - (r1 + r2)) < EPS || fabs(fabs(r1 - r2) - len) < EPS) {
  162.                 point d, c;
  163.                 long double r;
  164.                 if (r1 > r2)
  165.                         d = vec(c1,c2), c = c1, r = r1;
  166.                 else
  167.                         d = vec(c2,c1), c = c2, r = r2;
  168.                 res1 = res2 = normalize(d) * r + c;
  169.                 return 1;
  170.         }
  171.         if (len > r1 + r2 || len < fabs(r1 - r2))
  172.                 return 0;
  173.         long double a = cosRule(r2, r1, len);
  174.         point c1c2 = normalize(vec(c1,c2)) * r1;
  175.         res1 = rotate(c1c2,a) + c1;
  176.         res2 = rotate(c1c2,-a) + c1;
  177.         return 2;
  178. }
  179.  
  180. void circle2(const point& p1, const point& p2, point& cen, long double& r) {
  181.         cen = mid(p1,p2);
  182.         r = length(vec(p1,p2)) / 2;
  183. }
  184.  
  185. bool circle3(const point& p1, const point& p2, const point& p3, point& cen,
  186.                 long double& r) {
  187.         point m1 = mid(p1,p2);
  188.         point m2 = mid(p2,p3);
  189.         point perp1 = perp(vec(p1,p2));
  190.         point perp2 = perp(vec(p2,p3));
  191.         bool res = intersect(m1, m1 + perp1, m2, m2 + perp2, cen);
  192.         r = length(vec(cen,p1));
  193.         return res;
  194. }
  195.  
  196. STATE circlePoint(const point & cen, const long double & r, const point& p) {
  197.         long double lensqr = lengthSqr(vec(cen,p));
  198.         if (fabs(lensqr - r * r) < EPS)
  199.                 return BOUNDRY;
  200.         if (lensqr < r * r)
  201.                 return IN;
  202.         return OUT;
  203. }
  204.  
  205. int tangentPoints(const point & cen, const long double & r, const point& p,
  206.                 point &r1, point &r2) {
  207.         STATE s = circlePoint(cen, r, p);
  208.         if (s != OUT) {
  209.                 r1 = r2 = p;
  210.                 return s == BOUNDRY;
  211.         }
  212.         point cp = vec(cen,p);
  213.         long double h = length(cp);
  214.         long double a = acos(r / h);
  215.         cp = normalize(cp) * r;
  216.         r1 = rotate(cp,a) + cen;
  217.         r2 = rotate(cp,-a) + cen;
  218.         return 2;
  219. }
  220.  
  221. // minimum enclosing circle
  222. //init p array with the points and ps with the number of points
  223. //cen and rad are result circle
  224. //you must call random_shuffle(p,p+ps); before you call mec
  225. #define MAXPOINTS 100000
  226. point p[MAXPOINTS], r[3], cen;
  227. int ps, rs;
  228. long double rad;
  229.  
  230. void mec() {
  231.         if (rs == 3) {
  232.                 circle3(r[0], r[1], r[2], cen, rad);
  233.                 return;
  234.         }
  235.         if (rs == 2 && ps == 0) {
  236.                 circle2(r[0], r[1], cen, rad);
  237.                 return;
  238.         }
  239.         if (!ps) {
  240.                 cen = r[0];
  241.                 rad = 0;
  242.                 return;
  243.         }
  244.         ps--;
  245.         mec();
  246.         if (circlePoint(cen, rad, p[ps]) == OUT) {
  247.                 r[rs++] = p[ps];
  248.                 mec();
  249.                 rs--;
  250.         }
  251.         ps++;
  252.  
  253. }
  254.  
  255. //to check if the points are sorted anti-clockwise or clockwise
  256. //remove the fabs at the end and it will return -ve value if clockwise
  257. long double polygonArea(const vector<point>&p) {
  258.         long double res = 0;
  259.         for (int i = 0; i < sz(p); i++) {
  260.                 int j = (i + 1) % sz(p);
  261.                 res += cross(p[i],p[j]);
  262.         }
  263.         return fabs(res) / 2;
  264. }
  265.  
  266. // return the centroid point of the polygon
  267. // The centroid is also known as the "centre of gravity" or the "center of mass". The position of the centroid
  268. // assuming the polygon to be made of a material of uniform density.
  269. point polyginCentroid(vector<point> &polygon) {
  270.         point res(0, 0);
  271.         long double a = 0;
  272.  
  273.         for (int i = 0; i < (int) polygon.size(); i++) {
  274.                 int j = (i + 1) % polygon.size();
  275.                 long double x,y;
  276.                 x=res.X + (polygon[i].X + polygon[j].X) * (polygon[i].X * polygon[j].Y
  277.                                 - polygon[j].X * polygon[i].Y);
  278.  
  279.                 y=res.Y + (polygon[i].Y + polygon[j].Y) * (polygon[i].X * polygon[j].Y
  280.                                 - polygon[j].X * polygon[i].Y);
  281.                 res=point(x,y);
  282.                 a += polygon[i].X * polygon[j].Y - polygon[i].Y * polygon[j].X;
  283.         }
  284.  
  285.         a *= 0.5;
  286.         res/=point(6*a,0);
  287.  
  288.         return res;
  289. }
  290.  
  291. int picksTheorm(vector<point>& p) {
  292.         long double area = 0;
  293.         int bound = 0;
  294.         for (int i = 0; i < sz(p); i++) {
  295.                 int j = (i + 1) % sz(p);
  296.                 area += cross(p[i],p[j]);
  297.                 point v = vec(p[i],p[j]);
  298.                 bound += abs(__gcd((int) v.X, (int) v.Y));
  299.         }
  300.         area /= 2;
  301.         area = fabs(area);
  302.         return round(area - bound / 2 + 1);
  303. }
  304.  
  305. void polygonCut(const vector<point>& p, const point&a, const point&b, vector<
  306.                 point>& res) {
  307.         res.clear();
  308.         for (int i = 0; i < sz(p); i++) {
  309.                 int j = (i + 1) % sz(p);
  310.                 bool in1 = cross(vec(a,b),vec(a,p[i])) > EPS;
  311.                 bool in2 = cross(vec(a,b),vec(a,p[j])) > EPS;
  312.                 if (in1)
  313.                         res.push_back(p[i]);
  314.                 if (in1 ^ in2) {
  315.                         point r;
  316.                         intersect(a, b, p[i], p[j], r);
  317.                         res.push_back(r);
  318.                 }
  319.         }
  320. }
  321.  
  322. //assume that both are anti-clockwise
  323. void convexPolygonIntersect(const vector<point>& p, const vector<point>& q,
  324.                 vector<point>& res) {
  325.         res = q;
  326.         for (int i = 0; i < sz(p); i++) {
  327.                 int j = (i + 1) % sz(p);
  328.                 vector<point> temp;
  329.                 polygonCut(res, p[i], p[j], temp);
  330.                 res = temp;
  331.                 if (res.empty())
  332.                         return;
  333.         }
  334. }
  335.  
  336. void voronoi(const vector<point> &pnts, const vector<point>& rect, vector<
  337.                 vector<point> > &res) {
  338.         res.clear();
  339.         for (int i = 0; i < sz(pnts); i++) {
  340.                 res.push_back(rect);
  341.                 for (int j = 0; j < sz(pnts); j++) {
  342.                         if (j == i)
  343.                                 continue;
  344.                         point p = perp(vec(pnts[i],pnts[j]));
  345.                         point m = mid(pnts[i],pnts[j]);
  346.                         vector<point> temp;
  347.                         polygonCut(res.back(), m, m + p, temp);
  348.                         res.back() = temp;
  349.                 }
  350.         }
  351. }
  352.  
  353. STATE pointInPolygon(const vector<point>& p, const point &pnt) {
  354.         point p2 = pnt + point(1, 0);
  355.         int cnt = 0;
  356.         for (int i = 0; i < sz(p); i++) {
  357.                 int j = (i + 1) % sz(p);
  358.                 if (pointOnSegment(p[i], p[j], pnt))
  359.                         return BOUNDRY;
  360.                 point r;
  361.                 if(!intersect(pnt, p2, p[i], p[j], r))
  362.                         continue;
  363.                 if (!pointOnRay(pnt, p2, r))
  364.                         continue;
  365.                 if (same(r,p[i]) || same(r,p[j]))
  366.                         if (fabs(r.Y - min(p[i].Y, p[j].Y)) < EPS)
  367.                                 continue;
  368.                 if (!pointOnSegment(p[i], p[j], r))
  369.                         continue;
  370.                 cnt++;
  371.         }
  372.         return cnt & 1 ? IN : OUT;
  373. }
  374.  
  375. struct cmp {
  376.         point about;
  377.         cmp(point c) {
  378.                 about = c;
  379.         }
  380.         bool operator()(const point& p, const point& q) const {
  381.                 double cr = cross(vec(about, p), vec(about, q));
  382.                 if (fabs(cr) < EPS)
  383.                         return make_pair(p.Y, p.X) < make_pair(q.Y, q.X);
  384.                 return cr > 0;
  385.         }
  386. };
  387.  
  388. void sortAntiClockWise(vector<point>& pnts) {
  389.         point mn(1 / 0.0, 1 / 0.0);
  390.         for (int i = 0; i < sz(pnts); i++)
  391.                 if (make_pair(pnts[i].Y, pnts[i].X) < make_pair(mn.Y, mn.X))
  392.                         mn = pnts[i];
  393.  
  394.         sort(all(pnts), cmp(mn));
  395. }
  396.  
  397. void convexHull(vector<point> pnts, vector<point> &convex) {
  398.         sortAntiClockWise(pnts);
  399.         convex.clear();
  400.         convex.push_back(pnts[0]);
  401.         if (sz(pnts) == 1)
  402.                 return;
  403.         convex.push_back(pnts[1]);
  404.         if (sz(pnts) == 2) {
  405.                 if (same(pnts[0], pnts[1]))
  406.                         convex.pop_back();
  407.                 return;
  408.         }
  409.         for (int i = 2; i <= sz(pnts); i++) {
  410.                 point c = pnts[i % sz(pnts)];
  411.                 while (sz(convex) > 1) {
  412.                         point b = convex.back();
  413.                         point a = convex[sz(convex) - 2];
  414.                         if (cross(vec(b, a), vec(b, c)) < -EPS)
  415.                                 break;
  416.                         convex.pop_back();
  417.                 }
  418.                 if (i < sz(pnts))
  419.                         convex.push_back(pnts[i]);
  420.         }
  421. }
  422. int n,px,py,x[100005],y[100005];
  423. int main()
  424. {
  425.     cin>>n>>px>>py;
  426.     for(int i=0;i<n;++i){
  427.         scanf("%d%d",x+i,y+i);
  428.     }
  429.     x[n]=x[0];y[n]=y[0];
  430.     long double mn=1e15,mx=0;
  431.     for(int i=0;i<n;++i){
  432.         mx=max(mx,length(point(px,py)-point(x[i],y[i])));
  433.         mn=min(mn,pointSegmentDist(point(x[i],y[i]),point(x[i+1],y[i+1]),point(px,py)));
  434.     }
  435.     cout<<setprecision(10)<<fixed;
  436.     cout<<acos(-1)*(mx*mx-mn*mn)<<endl;
  437. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!