Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <string>
- #include <vector>
- #include <map>
- #include <list>
- #include <iterator>
- #include <set>
- #include <queue>
- #include <iostream>
- #include <sstream>
- #include <stack>
- #include <deque>
- #include <cmath>
- #include <memory.h>
- #include <cstdlib>
- #include <cstdio>
- #include <cctype>
- #include <algorithm>
- #include <utility>
- #include <cassert>
- #include <complex>
- #include <time.h>
- using namespace std;
- #define FOR(i, a, b) for(int i=(a);i<(b);i++)
- #define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
- #define FILL(A,value) memset(A,value,sizeof(A))
- #define ALL(V) V.begin(), V.end()
- #define SZ(V) (int)V.size()
- #define PB push_back
- #define MP make_pair
- #define pi 3.14159265358979
- #define x0 ikjnrmthklmnt
- #define y0 lkrjhkltr
- #define y1 ewrgrg
- typedef long long Int;
- typedef unsigned long long UInt;
- typedef vector<int> VI;
- typedef pair<int, int> PII;
- typedef complex<double> base;
- const int INF = 1000000000;
- const int MAX = 50000;
- const int MAXE = 5000;
- const int MAXV = 20*20;
- const int BASE = 1000000007;
- const int MOD = 1000000007;
- const double eps = 1e-6;
- struct Point
- {
- double x, y;
- Point() {};
- Point(double xx, double yy)
- {
- x = xx; y = yy;
- }
- Point operator -(Point p)
- {
- return Point(x-p.x, y-p.y);
- }
- Point operator +(Point p)
- {
- return Point(x+p.x, y+p.y);
- }
- double operator *(Point q)
- {
- return q.x*y - q.y*x;
- }
- static bool cmp1(Point p1, Point p2)
- {
- if (abs(p1.x - p2.x) > eps) return p1.x < p2.x;
- return p1.y < p2.y;
- }
- double dist2(Point p)
- {
- return (p.x - x)*(p.x - x) + (p.y - y)*(p.y - y);
- }
- double dist(Point p)
- {
- return sqrt(dist2(p));
- }
- Point cw(Point p, double angle)
- {
- p = p - *this;
- Point q;
- q.x = p.x*cos(angle) - p.y*sin(angle);
- q.y = p.x*sin(angle) + p.y*cos(angle);
- p = q + *this;
- return p;
- }
- };
- double vdob(Point p1, Point p2, Point p3)
- {
- return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
- }
- int dblcmp(double x) {
- return (x < -eps ? -1 : x > eps);
- }
- double vdob(Point p1, Point p2) {
- return p1.x * p2.y - p1.y * p2.x;
- }
- double dot(Point p1, Point p2) {
- return p1.x * p2.x + p1.y * p2.y;
- }
- struct Segment
- {
- Point p1, p2;
- double a, b, c;
- void init()
- {
- a = p2.y - p1.y;
- b = p1.x - p2.x;
- c = -a*p1.x - b*p1.y;
- }
- bool checkSegmIntersection(Segment s)
- {
- if (min(s.p1.x, s.p2.x) > max(p1.x, p2.x)) return false;
- if (min(s.p1.y, s.p2.y) > max(p1.y, p2.y)) return false;
- if (max(s.p1.x, s.p2.x) < min(p1.x, p2.x)) return false;
- if (max(s.p1.y, s.p2.y) < min(p1.y, p2.y)) return false;
- if (vdob(p1,p2,s.p1) * vdob(p1,p2,s.p2) < eps &&
- vdob(s.p1,s.p2,p1) * vdob(s.p1,s.p2,p2) < eps) return true;
- return false;
- }
- bool parallel(Segment s)
- {
- return abs(a*s.b - b*s.a) < eps;
- }
- vector<Point> getLineIntersection(Segment s)
- {
- vector<Point> e;
- if (parallel(s)) return e;
- 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)));
- return e;
- }
- double dist(Point p)
- {
- if (p.dist2(p1) + eps > p.dist2(p2) + p1.dist2(p2)) return p.dist(p2);
- if (p.dist2(p2) + eps > p.dist2(p1) + p1.dist2(p2)) return p.dist(p1);
- init();
- return abs(a*p.x + b*p.y + c)/sqrt(a*a+b*b);
- }
- double dist(Segment s)
- {
- if (checkSegmIntersection(s)) return 0;
- return min(min(dist(s.p1), dist(s.p2)),
- min(s.dist(p1), s.dist(p2)));
- }
- vector<Point> getSegmIntersection(Segment l)
- {
- vector<Point> e;
- if (abs(a*l.b - b*l.a) < eps) return e;
- if (vdob(p1,p2,l.p1)*vdob(p1,p2,l.p2) > eps ||
- vdob(l.p1,l.p2,p1)*vdob(l.p1,l.p2,p2) > eps) return e;
- Point p;
- p.y = (l.c*a-l.a*c)/(l.a*b-l.b*a);
- p.x = (l.c*b-l.b*c)/(a*l.b-b*l.a);
- e.PB(p);
- return e;
- };
- };
- const double maxd = 1e5;
- const int maxn = 200000;
- int cnt = 0;
- struct halfp {
- Point p1, p2;
- double a;
- halfp() { }
- halfp(Point tp1, Point tp2) : p1(tp1), p2(tp2) {
- tp2 = tp2 - tp1;
- a = atan2(tp2.y, tp2.x);
- }
- Segment getSegment()
- {
- Segment s;
- s.p1 = p1;
- s.p2 = p2;
- s.init();
- return s;
- }
- bool operator==(halfp r) const {
- return dblcmp(a - r.a) == 0;
- }
- bool operator<(halfp r) const {
- Point g = Point(p2.x - r.p1.x, p2.y - r.p1.y);
- if (dblcmp(a - r.a) == 0) return dblcmp(vdob(r.p2 - r.p1, g)) >= 0;
- else return a < r.a;
- }
- };
- vector<halfp> hp;
- void addhp(Point p1, Point p2) {
- cnt++;
- hp.PB(halfp(p1, p2));
- }
- bool checkhp(halfp h1, halfp h2, halfp h3) {
- vector<Point> p = h1.getSegment().getLineIntersection(h2.getSegment());
- return p.size() && dblcmp(vdob(p[0] - h3.p1, h3.p2 - h3.p1)) > 0;
- }
- vector<Point> hp_inter() {
- sort(hp.begin(), hp.end());
- cnt = unique(hp.begin(), hp.end()) - hp.begin();
- deque<halfp> DQ;
- DQ.push_back(hp[0]);
- DQ.push_back(hp[1]);
- for (int i = 2; i < cnt; ++i) {
- while (DQ.size() > 1 && checkhp(*----DQ.end(), *--DQ.end(), hp[i])) DQ.pop_back();
- while (DQ.size() > 1 && checkhp(*++DQ.begin(), *DQ.begin(), hp[i])) DQ.pop_front();
- DQ.push_back(hp[i]);
- }
- while (DQ.size() > 1 && checkhp(*----DQ.end(), *--DQ.end(), DQ.front())) DQ.pop_back();
- while (DQ.size() > 1 && checkhp(*++DQ.begin(), *DQ.begin(), DQ.back())) DQ.pop_front();
- DQ.push_front(DQ.back());
- vector<Point> res;
- while (DQ.size() > 1) {
- halfp tmp = DQ.front();
- DQ.pop_front();
- vector<Point> q = tmp.getSegment().getLineIntersection(DQ.front().getSegment());
- if (q.size()) res.push_back(q[0]);
- }
- //cout << res.size() << endl;
- //FOR (i,0,res.size()) cout << res[i].x<<" "<<res[i].y << endl;
- return res;
- }
- double area(vector<Point> D)
- {
- double s = 0;
- FOR (i,0,D.size())
- {
- s += D[i].y*D[(i+1)%SZ(D)].x - D[i].x*D[(i+1)%SZ(D)].y;
- }
- return s/2;
- }
- int h, w;
- int nx = 0, na = 0, nb = 0;
- string s[200];
- int ma1, ma2, mb1, mb2, mx;
- double allAx, allBx, allXx;
- double allAy, allBy, allXy;
- double ans = 0;
- bool ADD(double a, double b, double c)
- {
- //cout << a<<" "<<b<<" "<<c<<endl;
- if (abs(a) > eps)
- {
- if (a > 0) addhp(Point((c-b)/a,1), Point(c/a,0));
- else addhp(Point((c+b)/a,-1), Point(c/a,0));
- return 1;
- }
- else
- if (abs(b) > eps)
- {
- if (b > 0) addhp(Point(1,(c-a)/b), Point(0,c/b));
- else addhp(Point(-1,(c+a)/b), Point(0,c/b));
- return 1;
- }
- if (c < eps) return 1;
- return 0;
- }
- int main()
- {
- //freopen("/Users/Taras/Desktop/Trumen/Program 6-7(T)/Tests/input/input30.txt", "r", stdin);
- //freopen("/Users/Taras/Desktop/Trumen/Program 6-7(T)/Tests/output/output30.txt", "w", stdout);
- cin >> h >> w;
- cin >> ma1 >> ma2 >> mb1 >> mb2 >> mx;
- FOR (i,0,h)
- cin >> s[i];
- //L.PB(Line{1,0,ma1});
- //L.PB(Line{0,1,mb1});
- //L.PB(Line{-1,0,-ma2});
- //L.PB(Line{0,-1,-mb2});
- FOR (i,0,h)
- FOR (j,0,w)
- {
- if (s[i][j] == 'X') nx++, allXx += i + 0.5, allXy += j + 0.5;
- if (s[i][j] == 'A') na++, allAx += i + 0.5, allAy += j + 0.5;
- if (s[i][j] == 'B') nb++, allBx += i + 0.5, allBy += j + 0.5;
- }
- FOR (i,0,h)
- FOR (j,0,w)
- {
- if (s[i][j] == '.') continue;
- hp.clear();
- addhp(Point(ma1, 1), Point(ma1, 0));
- addhp(Point(0, mb1), Point(1,mb1));
- addhp(Point(ma2, 0), Point(ma2,1));
- addhp(Point(1, mb2), Point(0,mb2));
- bool ok = 1;
- ok &= ADD(allAx - na*i, allBx - nb*i, i*mx*nx - allXx*mx);
- ok &= ADD(allAy - na*j, allBy - nb*j, j*mx*nx - allXy*mx);
- ok &= ADD(-(allAx - na*(i+1)), -(allBx - nb*(i+1)), -((i+1)*mx*nx - allXx*mx));
- ok &= ADD(-(allAy - na*(j+1)), -(allBy - nb*(j+1)), -((j+1)*mx*nx - allXy*mx));
- //L.PB(Line{allAx - na*i, allBx - nb*i, i*mx*nx - allXx*mx});
- //L.PB(Line{allAy - na*j, allBy - nb*j, j*mx*nx - allXy*mx});
- //L.PB(Line{-(allAx - na*(i+1)), -(allBx - nb*(i+1)), -((i+1)*mx*nx - allXx*mx)});
- //L.PB(Line{-(allAy - na*(j+1)), -(allBy - nb*(j+1)), -((j+1)*mx*nx - allXy*mx)});
- if (ok) ans += abs(area(hp_inter()));
- }
- printf("%.13lf", ans / (ma2 - ma1) / (mb2 - mb1));
- return 0;
- }
- /*
- 10 10
- 1 100 1 100 1
- AXXXXXXXXX
- X........X
- X........X
- X..XXXXXXX
- X........X
- XXXXXX...X
- X........X
- X......X.X
- X......X.X
- XXXXXXXXXB
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement