Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// Sunt un tractorel :D ( comentariu adaugat ulterior pentru Luci :D )
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cmath>
- #define Nmax 55
- #define EPS 0.00001
- using namespace std;
- int N,M,nrn,vf = 2;
- pair<int,int> pointsN[Nmax],pointsM[Nmax];
- pair<double,double> thenew[Nmax];
- pair<double,double> S[Nmax*Nmax];
- double Px,Py;
- int _gcd(int a,int b)
- {
- if(b) return _gcd(b,a%b);
- return a;
- }
- void read()
- {
- int a,b;
- scanf("%d",&N);
- for(int i = 1; i <= N; ++i){
- scanf("%d%d",&a,&b);
- pointsN[i] = make_pair(a,b);
- }
- scanf("%d",&M);
- for(int i = 1; i <= M; ++i){
- scanf("%d%d",&a,&b);
- pointsM[i] = make_pair(a,b);
- }
- pointsN[N+1] = pointsN[1];
- pointsM[M+1] = pointsM[1];
- }
- /**
- A.first A.second 1
- B.first B.second 1 = A.first*B.second + B.first*C.second + C.first*A.second - C.first*B.second - C.second*A.first - B.first*A.second
- C.first C.second 1
- **/
- int side(pair<int,int> A,pair<int,int> B,pair<int,int> C)
- {
- return A.first*B.second + B.first*C.second + C.first*A.second -
- C.first*B.second - C.second*A.first - B.first*A.second;
- }
- void GET_interiorPOINTS1()
- { /// ne bazam pe faptul ca deja sunt date in ordine cele doua poligoane
- int _x,_y,S1,S2,i,tip;
- pair<int,int> pc;
- for(int j = 1; j <= N; ++j)
- {
- _x = pointsN[j].first;
- _y = pointsN[j].second;
- pc = make_pair(_x,_y);
- tip = 0; /// nu stim daca e trigo sau invers sensul
- for(i = 1; i <= M - 1; ++i)
- {
- S1 = side(pointsM[i],pointsM[i+1],pc);
- S2 = side(pointsM[i+1],pointsM[i+2],pc);
- if(S1 == 0 && S2 == 0)continue; /// nu stim sensul
- if(S1 >= 0 && S2 >= 0){
- if(!tip){tip = 1;continue;}
- }
- else if(tip == 1) break;
- if(S1 <= 0 && S2 <= 0){
- if(!tip){tip = 2;continue;}
- }
- else if(tip == 2) break;
- if(S1 > 0 && S2 < 0 || S1 < 0 && S2 > 0) break;
- }
- if(i == M)
- thenew[++nrn] = pc;
- }
- }
- void GET_interiorPOINTS2()
- { /// ne bazam pe faptul ca deja sunt date in ordine cele doua poligoane
- int _x,_y,S1,S2,i,tip;
- pair<int,int> pc;
- for(int j = 1; j <= M; ++j)
- {
- _x = pointsM[j].first;
- _y = pointsM[j].second;
- pc = make_pair(_x,_y);
- tip = 0; /// nu stim daca e trigo sau invers sensul
- for(i = 1; i <= N - 1; ++i)
- {
- S1 = side(pointsN[i],pointsN[i+1],pc);
- S2 = side(pointsN[i+1],pointsN[i+2],pc);
- if(S1 == 0 && S2 == 0) continue; /// nu stim sensul
- if(S1 >= 0 && S2 >= 0){
- if(!tip){tip = 1;continue;}
- }
- else if(tip == 1) break;
- if(S1 <= 0 && S2 <= 0){
- if(!tip){tip = 2;continue;}
- }
- else if(tip == 2) break;
- if(S1 > 0 && S2 < 0 || S1 < 0 && S2 > 0) break; /// daca sunt de o parte si de alta
- }
- if(i == N)
- thenew[++nrn] = pc;
- }
- }
- int ecA(pair<int,int> A,pair<int,int> B)
- {
- return A.second - B.second;
- }
- int ecB(pair<int,int> A,pair<int,int> B)
- {
- return B.first - A.first;
- }
- int ecC(pair<int,int> A,pair<int,int> B)
- {
- return A.first*(B.second - A.second) +
- A.second*(A.first - B.first);
- }
- int panta(pair<int,int> A,pair<int,int> B,pair<int,int> A2,pair<int,int> B2)
- {
- return (B.second - A.second)*(B2.first - A2.first) == (B.first - A.first)*(B2.second - A2.second);
- }
- int apartine(pair<int,int> A ,pair<int,int> B,pair<double,double> P)
- {
- if(A.first > B.first) swap ( A.first, B.first);
- if(A.second > B.second) swap ( A.second, B.second );
- if(A.first <= P.first + EPS && P.first - EPS <= B.first &&
- A.second <= P.second + EPS && P.second - EPS <= B.second )
- return 1;
- return 0;
- }
- void baga(pair<int,int> A,pair<int,int> B,pair<int,int> A2,pair<int,int> B2)
- {
- if(A.first > B.first) swap(A,B);
- if(A2.first > B2.first) swap(A2,B2);/// punem bine capetele
- /// avem patru cazuri separate
- double stX,stY,drX,drY;
- pair<double,double> P1,P2;
- if(B.first < A2.first) return; /// e prea la stanga
- if(A.first > B2.first) return; /// e prea la dreatpa
- if(A.first <= A2.first)
- {
- stX = A2.first;
- stY = A2.second;
- if(B.first <= B2.first && B.first >= A2.first)
- {
- drX = B.first;for(int i = 1; i <= vf+1; ++i)
- {
- S[i].first += 10000;
- S[i].second += 10000;
- }
- drY = B.second;
- }
- else if(B.first >= A2.first && B.first >= B2.first)
- {
- drX = B2.first;
- drY = B2.second;
- }
- }
- else
- if(A.first <= B2.first) /// A deja e pe dreapta A2B2
- {
- stX = A.first;
- stY = A.second;
- if(B.first <= B2.first) /// deja stim ca e unde trebuie
- {
- drX = B.first;
- drY = B.second;
- }
- else {
- drX = B2.first;
- drY = B2.second;
- }
- }
- P1 = make_pair(stX,stY);
- P2 = make_pair(drX,drY);
- if(stX != drX && stY != drY)
- {
- if(apartine(A,B,P1) && apartine(A2,B2,P1))
- thenew[++nrn] = P1;
- if(apartine(A,B,P2) && apartine(A2,B2,P2))
- thenew[++nrn] = P2;
- return;
- }
- if(apartine(A,B,P1) && apartine(A2,B2,P1))
- thenew[++nrn] = make_pair(stX,stY); /// practic doar in capat s-au intersectat
- }
- void GET_intersections()
- {
- int a1,b1,c1,a2,b2,c2,cmn;
- double _newx,_newy;
- pair<double,double>pct;
- for(int i = 1; i <= N; ++i)
- {
- a1 = ecA(pointsN[i],pointsN[i+1]);
- b1 = ecB(pointsN[i],pointsN[i+1]);
- c1 = ecC(pointsN[i],pointsN[i+1]);
- cmn = _gcd(a1,_gcd(b1,c1));
- a1 /= cmn;b1 /= cmn;c1 /= cmn;
- if(a1 < 0) a1 *= -1, b1 *= -1, c1 *= -1;
- for(int j = 1; j <= M; ++j)
- {
- a2 = ecA(pointsM[j],pointsM[j+1]);
- b2 = ecB(pointsM[j],pointsM[j+1]);
- c2 = ecC(pointsM[j],pointsM[j+1]);
- cmn = _gcd(a2,_gcd(b2,c2));
- a2 /= cmn;b2 /= cmn;c2 /= cmn;
- if(a2 < 0) a2 *= -1, b2 *= -1, c2 *= -1;
- if(panta(pointsN[i],pointsN[i+1] , pointsM[j],pointsM[j+1]) ){ /// aici nu stim exact ce se intampla ( trebuie sa coincida dreptele )
- if(a1 != a2 || b1 != b2 || c1 != c2)
- continue;
- baga(pointsN[i],pointsN[i+1],pointsM[j],pointsM[j+1]);
- }
- _newx = (c2*b1 - c1*b2)/((double) a1*b2 - a2*b1);
- _newy = (c2*a1 - c1*a2)/((double) b1*a2 - b2*a1);
- pct = make_pair(_newx,_newy);
- if(apartine(pointsN[i],pointsN[i+1],pct) &&
- apartine(pointsM[j],pointsM[j+1],pct))
- thenew[++nrn] = pct;
- }
- }
- }
- double cross(pair<double,double> A, pair<double,double> B, pair<double,double> C)
- {
- return A.first * B.second + B.first * C.second + C.first * A.second
- - C.first * B.second - C.second * A.first - B.first * A.second;
- }
- class cmp{
- public:
- bool operator()(const pair<double,double> A, const pair<double,double> B)const
- {
- return cross(thenew[1],A,B)<0;
- }
- };
- class cmp2{
- public:
- bool operator() (const pair<double,double> A,const pair<double,double> B)const
- {
- return atan2(A.second-Py,A.first-Px) < atan2(B.second-Py,B.first-Px);
- }
- };
- void sorteaza2()
- {
- for(int i = 1; i <= nrn; ++i)
- Px += thenew[i].first,Py += thenew[i].second;
- Px /= nrn;
- Py /= nrn;
- sort(thenew+1,thenew+nrn+1,cmp2());
- }
- void sorteaza()
- {
- int pz = 1;
- for(int i = 2; i <= nrn; ++i)
- if(thenew[i] < thenew[pz])
- pz = i;
- swap(thenew[pz],thenew[1]);
- sort(thenew+2,thenew+nrn+1,cmp());
- }
- void convex_hull2()
- {
- for(int i = 1; i <= nrn; ++i)
- S[i] = thenew[i];
- S[nrn+1] = S[1];
- vf = nrn;
- }
- void convex_hull()
- {
- S[1] = thenew[1];
- S[2] = thenew[2];
- for(int i = 3; i <= nrn; ++i)
- {
- while(vf >= 2 && cross(S[vf-1],S[vf],thenew[i]) > 0)
- --vf;
- S[++vf] = thenew[i];
- }
- }
- double areaT;
- double abso(double x)
- {
- if(x > 0) return x; return -x;
- }
- double arie(pair<double,double> A,pair<double,double> B) ///( dublul ariei )
- {
- return (double)( abso(A.second) + abso(B.second) ) * (double)(B.first-A.first) /2;
- }
- #include <fstream>
- #include <iomanip>
- void get_arie()
- {
- ofstream fout("arie.out");
- S[vf+1] = S[1];
- for(int i = 1; i <= vf+1; ++i)
- {
- S[i].first += 10000;
- S[i].second += 10000;
- }
- for(int i = 1; i <= vf; ++i)
- areaT += arie(S[i],S[i+1]);
- ///printf("%.3lf\n",abso(areaT));
- areaT = abso(areaT);
- fout << setprecision(3) << fixed;
- if(areaT > 0.002)
- fout << areaT;
- else
- fout << "0.000";
- }
- int main()
- {
- freopen("arie.in","r",stdin);
- freopen("arie.out","w",stdout);
- read();
- GET_interiorPOINTS1();
- GET_interiorPOINTS2();
- GET_intersections();
- sorteaza2();
- convex_hull2();
- get_arie();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement