Advertisement
jeff69

Untitled

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