Advertisement
jeff69

Untitled

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