Advertisement
trumen_

Untitled

May 4th, 2016
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.97 KB | None | 0 0
  1. #include <string>
  2. #include <vector>
  3. #include <map>
  4. #include <list>
  5. #include <iterator>
  6. #include <set>
  7. #include <queue>
  8. #include <iostream>
  9. #include <sstream>
  10. #include <stack>
  11. #include <deque>
  12. #include <cmath>
  13. #include <memory.h>
  14. #include <cstdlib>
  15. #include <cstdio>
  16. #include <cctype>
  17. #include <algorithm>
  18. #include <utility>
  19. #include <cassert>
  20. #include <complex>
  21. #include <time.h>
  22. using namespace std;
  23.  
  24. #define FOR(i, a, b) for(int i=(a);i<(b);i++)
  25. #define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
  26. #define FILL(A,value) memset(A,value,sizeof(A))
  27.  
  28. #define ALL(V) V.begin(), V.end()
  29. #define SZ(V) (int)V.size()
  30. #define PB push_back
  31. #define MP make_pair
  32. #define pi 3.14159265358979
  33. #define x0 ikjnrmthklmnt
  34. #define y0 lkrjhkltr
  35. #define y1 ewrgrg
  36.  
  37. typedef long long Int;
  38. typedef unsigned long long UInt;
  39. typedef vector<int> VI;
  40. typedef pair<int, int> PII;
  41. typedef complex<double> base;
  42.  
  43. const int INF = 1000000000;
  44. const int MAX = 50000;
  45. const int MAXE = 5000;
  46. const int MAXV = 20*20;
  47. const int BASE = 1000000007;
  48. const int MOD = 1000000007;
  49.  
  50. const double eps = 1e-6;
  51.  
  52. struct Point
  53. {
  54. double x, y;
  55.  
  56. Point() {};
  57.  
  58. Point(double xx, double yy)
  59. {
  60. x = xx; y = yy;
  61. }
  62.  
  63. Point operator -(Point p)
  64. {
  65. return Point(x-p.x, y-p.y);
  66. }
  67.  
  68. Point operator +(Point p)
  69. {
  70. return Point(x+p.x, y+p.y);
  71. }
  72.  
  73. double operator *(Point q)
  74. {
  75. return q.x*y - q.y*x;
  76. }
  77.  
  78. static bool cmp1(Point p1, Point p2)
  79. {
  80. if (abs(p1.x - p2.x) > eps) return p1.x < p2.x;
  81. return p1.y < p2.y;
  82. }
  83.  
  84. double dist2(Point p)
  85. {
  86. return (p.x - x)*(p.x - x) + (p.y - y)*(p.y - y);
  87. }
  88.  
  89. double dist(Point p)
  90. {
  91. return sqrt(dist2(p));
  92. }
  93.  
  94. Point cw(Point p, double angle)
  95. {
  96. p = p - *this;
  97. Point q;
  98. q.x = p.x*cos(angle) - p.y*sin(angle);
  99. q.y = p.x*sin(angle) + p.y*cos(angle);
  100. p = q + *this;
  101. return p;
  102. }
  103.  
  104. };
  105.  
  106. double vdob(Point p1, Point p2, Point p3)
  107. {
  108. return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
  109. }
  110.  
  111. int dblcmp(double x) {
  112. return (x < -eps ? -1 : x > eps);
  113. }
  114.  
  115. double vdob(Point p1, Point p2) {
  116. return p1.x * p2.y - p1.y * p2.x;
  117. }
  118.  
  119. double dot(Point p1, Point p2) {
  120. return p1.x * p2.x + p1.y * p2.y;
  121. }
  122.  
  123. struct Segment
  124. {
  125. Point p1, p2;
  126. double a, b, c;
  127.  
  128. void init()
  129. {
  130. a = p2.y - p1.y;
  131. b = p1.x - p2.x;
  132. c = -a*p1.x - b*p1.y;
  133. }
  134.  
  135. bool checkSegmIntersection(Segment s)
  136. {
  137. if (min(s.p1.x, s.p2.x) > max(p1.x, p2.x)) return false;
  138. if (min(s.p1.y, s.p2.y) > max(p1.y, p2.y)) return false;
  139. if (max(s.p1.x, s.p2.x) < min(p1.x, p2.x)) return false;
  140. if (max(s.p1.y, s.p2.y) < min(p1.y, p2.y)) return false;
  141.  
  142. if (vdob(p1,p2,s.p1) * vdob(p1,p2,s.p2) < eps &&
  143. vdob(s.p1,s.p2,p1) * vdob(s.p1,s.p2,p2) < eps) return true;
  144. return false;
  145. }
  146.  
  147. bool parallel(Segment s)
  148. {
  149. return abs(a*s.b - b*s.a) < eps;
  150. }
  151.  
  152. vector<Point> getLineIntersection(Segment s)
  153. {
  154. vector<Point> e;
  155. if (parallel(s)) return e;
  156. e.PB(Point((s.c*b - c*s.b)/(a*s.b - b*s.a), (s.c*a - c*s.a)/(b*s.a - a*s.b)));
  157. return e;
  158. }
  159.  
  160. double dist(Point p)
  161. {
  162. if (p.dist2(p1) + eps > p.dist2(p2) + p1.dist2(p2)) return p.dist(p2);
  163. if (p.dist2(p2) + eps > p.dist2(p1) + p1.dist2(p2)) return p.dist(p1);
  164. init();
  165. return abs(a*p.x + b*p.y + c)/sqrt(a*a+b*b);
  166. }
  167.  
  168. double dist(Segment s)
  169. {
  170. if (checkSegmIntersection(s)) return 0;
  171. return min(min(dist(s.p1), dist(s.p2)),
  172. min(s.dist(p1), s.dist(p2)));
  173. }
  174.  
  175.  
  176. vector<Point> getSegmIntersection(Segment l)
  177. {
  178. vector<Point> e;
  179. if (abs(a*l.b - b*l.a) < eps) return e;
  180. if (vdob(p1,p2,l.p1)*vdob(p1,p2,l.p2) > eps ||
  181. vdob(l.p1,l.p2,p1)*vdob(l.p1,l.p2,p2) > eps) return e;
  182. Point p;
  183. p.y = (l.c*a-l.a*c)/(l.a*b-l.b*a);
  184. p.x = (l.c*b-l.b*c)/(a*l.b-b*l.a);
  185. e.PB(p);
  186. return e;
  187. };
  188. };
  189.  
  190. const double maxd = 1e5;
  191. const int maxn = 200000;
  192. int cnt = 0;
  193.  
  194. struct halfp {
  195. Point p1, p2;
  196. double a;
  197.  
  198. halfp() { }
  199. halfp(Point tp1, Point tp2) : p1(tp1), p2(tp2) {
  200. tp2 = tp2 - tp1;
  201. a = atan2(tp2.y, tp2.x);
  202. }
  203.  
  204. Segment getSegment()
  205. {
  206. Segment s;
  207. s.p1 = p1;
  208. s.p2 = p2;
  209. s.init();
  210. return s;
  211. }
  212.  
  213. bool operator==(halfp r) const {
  214. return dblcmp(a - r.a) == 0;
  215. }
  216. bool operator<(halfp r) const {
  217. Point g = Point(p2.x - r.p1.x, p2.y - r.p1.y);
  218. if (dblcmp(a - r.a) == 0) return dblcmp(vdob(r.p2 - r.p1, g)) >= 0;
  219. else return a < r.a;
  220. }
  221. };
  222.  
  223. vector<halfp> hp;
  224.  
  225. void addhp(Point p1, Point p2) {
  226. cnt++;
  227. hp.PB(halfp(p1, p2));
  228. }
  229.  
  230. bool checkhp(halfp h1, halfp h2, halfp h3) {
  231. vector<Point> p = h1.getSegment().getLineIntersection(h2.getSegment());
  232. return p.size() && dblcmp(vdob(p[0] - h3.p1, h3.p2 - h3.p1)) > 0;
  233. }
  234.  
  235. vector<Point> hp_inter() {
  236. sort(hp.begin(), hp.end());
  237. cnt = unique(hp.begin(), hp.end()) - hp.begin();
  238. deque<halfp> DQ;
  239. DQ.push_back(hp[0]);
  240. DQ.push_back(hp[1]);
  241. for (int i = 2; i < cnt; ++i) {
  242. while (DQ.size() > 1 && checkhp(*----DQ.end(), *--DQ.end(), hp[i])) DQ.pop_back();
  243. while (DQ.size() > 1 && checkhp(*++DQ.begin(), *DQ.begin(), hp[i])) DQ.pop_front();
  244. DQ.push_back(hp[i]);
  245. }
  246. while (DQ.size() > 1 && checkhp(*----DQ.end(), *--DQ.end(), DQ.front())) DQ.pop_back();
  247. while (DQ.size() > 1 && checkhp(*++DQ.begin(), *DQ.begin(), DQ.back())) DQ.pop_front();
  248. DQ.push_front(DQ.back());
  249. vector<Point> res;
  250. while (DQ.size() > 1) {
  251. halfp tmp = DQ.front();
  252. DQ.pop_front();
  253. vector<Point> q = tmp.getSegment().getLineIntersection(DQ.front().getSegment());
  254. if (q.size()) res.push_back(q[0]);
  255. }
  256. //cout << res.size() << endl;
  257. //FOR (i,0,res.size()) cout << res[i].x<<" "<<res[i].y << endl;
  258. return res;
  259. }
  260.  
  261. double area(vector<Point> D)
  262. {
  263. double s = 0;
  264. FOR (i,0,D.size())
  265. {
  266. s += D[i].y*D[(i+1)%SZ(D)].x - D[i].x*D[(i+1)%SZ(D)].y;
  267. }
  268. return s/2;
  269. }
  270.  
  271.  
  272. int h, w;
  273. int nx = 0, na = 0, nb = 0;
  274. string s[200];
  275. int ma1, ma2, mb1, mb2, mx;
  276. double allAx, allBx, allXx;
  277. double allAy, allBy, allXy;
  278. double ans = 0;
  279.  
  280. bool ADD(double a, double b, double c)
  281. {
  282. //cout << a<<" "<<b<<" "<<c<<endl;
  283. if (abs(a) > eps)
  284. {
  285. if (a > 0) addhp(Point((c-b)/a,1), Point(c/a,0));
  286. else addhp(Point((c+b)/a,-1), Point(c/a,0));
  287. return 1;
  288. }
  289. else
  290. if (abs(b) > eps)
  291. {
  292. if (b > 0) addhp(Point(1,(c-a)/b), Point(0,c/b));
  293. else addhp(Point(-1,(c+a)/b), Point(0,c/b));
  294. return 1;
  295. }
  296. if (c < eps) return 1;
  297. return 0;
  298. }
  299. int main()
  300. {
  301. //freopen("/Users/Taras/Desktop/Trumen/Program 6-7(T)/Tests/input/input30.txt", "r", stdin);
  302. //freopen("/Users/Taras/Desktop/Trumen/Program 6-7(T)/Tests/output/output30.txt", "w", stdout);
  303.  
  304. cin >> h >> w;
  305. cin >> ma1 >> ma2 >> mb1 >> mb2 >> mx;
  306. FOR (i,0,h)
  307. cin >> s[i];
  308.  
  309. //L.PB(Line{1,0,ma1});
  310. //L.PB(Line{0,1,mb1});
  311. //L.PB(Line{-1,0,-ma2});
  312. //L.PB(Line{0,-1,-mb2});
  313.  
  314. FOR (i,0,h)
  315. FOR (j,0,w)
  316. {
  317. if (s[i][j] == 'X') nx++, allXx += i + 0.5, allXy += j + 0.5;
  318. if (s[i][j] == 'A') na++, allAx += i + 0.5, allAy += j + 0.5;
  319. if (s[i][j] == 'B') nb++, allBx += i + 0.5, allBy += j + 0.5;
  320. }
  321.  
  322. FOR (i,0,h)
  323. FOR (j,0,w)
  324. {
  325. if (s[i][j] == '.') continue;
  326. hp.clear();
  327. addhp(Point(ma1, 1), Point(ma1, 0));
  328. addhp(Point(0, mb1), Point(1,mb1));
  329. addhp(Point(ma2, 0), Point(ma2,1));
  330. addhp(Point(1, mb2), Point(0,mb2));
  331. bool ok = 1;
  332. ok &= ADD(allAx - na*i, allBx - nb*i, i*mx*nx - allXx*mx);
  333. ok &= ADD(allAy - na*j, allBy - nb*j, j*mx*nx - allXy*mx);
  334. ok &= ADD(-(allAx - na*(i+1)), -(allBx - nb*(i+1)), -((i+1)*mx*nx - allXx*mx));
  335. ok &= ADD(-(allAy - na*(j+1)), -(allBy - nb*(j+1)), -((j+1)*mx*nx - allXy*mx));
  336.  
  337. //L.PB(Line{allAx - na*i, allBx - nb*i, i*mx*nx - allXx*mx});
  338. //L.PB(Line{allAy - na*j, allBy - nb*j, j*mx*nx - allXy*mx});
  339. //L.PB(Line{-(allAx - na*(i+1)), -(allBx - nb*(i+1)), -((i+1)*mx*nx - allXx*mx)});
  340. //L.PB(Line{-(allAy - na*(j+1)), -(allBy - nb*(j+1)), -((j+1)*mx*nx - allXy*mx)});
  341.  
  342. if (ok) ans += abs(area(hp_inter()));
  343. }
  344.  
  345. printf("%.13lf", ans / (ma2 - ma1) / (mb2 - mb1));
  346.  
  347. return 0;
  348. }
  349.  
  350. /*
  351. 10 10
  352. 1 100 1 100 1
  353. AXXXXXXXXX
  354. X........X
  355. X........X
  356. X..XXXXXXX
  357. X........X
  358. XXXXXX...X
  359. X........X
  360. X......X.X
  361. X......X.X
  362. XXXXXXXXXB
  363. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement