Advertisement
Guest User

Untitled

a guest
Mar 31st, 2015
192
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.43 KB | None | 0 0
  1. /// Sunt un tractorel :D ( comentariu adaugat ulterior pentru Luci :D )
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cstdio>
  6. #include <cmath>
  7.  
  8. #define Nmax 55
  9. #define EPS 0.00001
  10.  
  11. using namespace std;
  12. int N,M,nrn,vf = 2;
  13. pair<int,int> pointsN[Nmax],pointsM[Nmax];
  14. pair<double,double> thenew[Nmax];
  15. pair<double,double> S[Nmax*Nmax];
  16. double Px,Py;
  17.  
  18. int _gcd(int a,int b)
  19. {
  20.     if(b) return _gcd(b,a%b);
  21.     return a;
  22. }
  23.  
  24. void read()
  25. {
  26.     int a,b;
  27.     scanf("%d",&N);
  28.     for(int i = 1; i <= N; ++i){
  29.         scanf("%d%d",&a,&b);
  30.         pointsN[i] = make_pair(a,b);
  31.     }
  32.     scanf("%d",&M);
  33.     for(int i = 1; i <= M; ++i){
  34.         scanf("%d%d",&a,&b);
  35.         pointsM[i] = make_pair(a,b);
  36.     }
  37.     pointsN[N+1] = pointsN[1];
  38.     pointsM[M+1] = pointsM[1];
  39. }
  40.  
  41. /**
  42.  A.first A.second 1
  43.  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
  44.  C.first C.second 1
  45. **/
  46.  
  47. int side(pair<int,int> A,pair<int,int> B,pair<int,int> C)
  48. {
  49.     return A.first*B.second + B.first*C.second + C.first*A.second -
  50.            C.first*B.second - C.second*A.first - B.first*A.second;
  51. }
  52.  
  53. void GET_interiorPOINTS1()
  54. { /// ne bazam pe faptul ca deja sunt date in ordine cele doua poligoane
  55.     int _x,_y,S1,S2,i,tip;
  56.     pair<int,int> pc;
  57.     for(int j = 1; j <= N; ++j)
  58.     {
  59.         _x = pointsN[j].first;
  60.         _y = pointsN[j].second;
  61.         pc = make_pair(_x,_y);
  62.         tip = 0; /// nu stim daca e trigo sau invers sensul
  63.         for(i = 1; i <= M - 1; ++i)
  64.         {
  65.             S1 = side(pointsM[i],pointsM[i+1],pc);
  66.             S2 = side(pointsM[i+1],pointsM[i+2],pc);
  67.  
  68.             if(S1 == 0 && S2 == 0)continue; /// nu stim sensul
  69.  
  70.  
  71.             if(S1 >= 0 && S2 >= 0){
  72.                 if(!tip){tip = 1;continue;}
  73.             }
  74.             else if(tip == 1) break;
  75.  
  76.             if(S1 <= 0 && S2 <= 0){
  77.                 if(!tip){tip = 2;continue;}
  78.             }
  79.             else if(tip == 2) break;
  80.  
  81.             if(S1 > 0 && S2 < 0 || S1 < 0 && S2 > 0) break;
  82.         }
  83.         if(i == M)
  84.             thenew[++nrn] = pc;
  85.     }
  86. }
  87. void GET_interiorPOINTS2()
  88. { /// ne bazam pe faptul ca deja sunt date in ordine cele doua poligoane
  89.     int _x,_y,S1,S2,i,tip;
  90.     pair<int,int> pc;
  91.     for(int j = 1; j <= M; ++j)
  92.     {
  93.         _x = pointsM[j].first;
  94.         _y = pointsM[j].second;
  95.         pc = make_pair(_x,_y);
  96.         tip = 0; /// nu stim daca e trigo sau invers sensul
  97.         for(i = 1; i <= N - 1; ++i)
  98.         {
  99.             S1 = side(pointsN[i],pointsN[i+1],pc);
  100.             S2 = side(pointsN[i+1],pointsN[i+2],pc);
  101.  
  102.             if(S1 == 0 && S2 == 0)  continue; /// nu stim sensul
  103.  
  104.             if(S1 >= 0 && S2 >= 0){
  105.                 if(!tip){tip = 1;continue;}
  106.             }
  107.             else if(tip == 1) break;
  108.  
  109.             if(S1 <= 0 && S2 <= 0){
  110.                 if(!tip){tip = 2;continue;}
  111.             }
  112.             else if(tip == 2) break;
  113.  
  114.             if(S1 > 0 && S2 < 0 || S1 < 0 && S2 > 0) break; /// daca sunt de o parte si de alta
  115.         }
  116.         if(i == N)
  117.             thenew[++nrn] = pc;
  118.     }
  119. }
  120.  
  121. int ecA(pair<int,int> A,pair<int,int> B)
  122. {
  123.     return A.second - B.second;
  124. }
  125. int ecB(pair<int,int> A,pair<int,int> B)
  126. {
  127.     return B.first - A.first;
  128. }
  129. int ecC(pair<int,int> A,pair<int,int> B)
  130. {
  131.     return A.first*(B.second - A.second) +
  132.            A.second*(A.first - B.first);
  133. }
  134.  
  135. int panta(pair<int,int> A,pair<int,int> B,pair<int,int> A2,pair<int,int> B2)
  136. {
  137.     return (B.second - A.second)*(B2.first - A2.first) == (B.first - A.first)*(B2.second - A2.second);
  138. }
  139.  
  140. int apartine(pair<int,int> A ,pair<int,int> B,pair<double,double> P)
  141. {
  142.     if(A.first > B.first) swap ( A.first, B.first);
  143.     if(A.second > B.second) swap ( A.second, B.second );
  144.  
  145.     if(A.first <= P.first + EPS && P.first - EPS <= B.first &&
  146.        A.second <= P.second + EPS && P.second - EPS <= B.second )
  147.             return 1;
  148.     return 0;
  149.  
  150. }
  151.  
  152. void baga(pair<int,int> A,pair<int,int> B,pair<int,int> A2,pair<int,int> B2)
  153. {
  154.     if(A.first > B.first) swap(A,B);
  155.     if(A2.first > B2.first) swap(A2,B2);/// punem bine capetele
  156.  
  157.     /// avem patru cazuri separate
  158.     double stX,stY,drX,drY;
  159.     pair<double,double> P1,P2;
  160.     if(B.first < A2.first) return; /// e prea la stanga
  161.     if(A.first > B2.first) return; /// e prea la dreatpa
  162.  
  163.     if(A.first <= A2.first)
  164.     {
  165.         stX = A2.first;
  166.         stY = A2.second;
  167.         if(B.first <= B2.first && B.first >= A2.first)
  168.         {
  169.             drX = B.first;for(int i = 1; i <= vf+1; ++i)
  170.     {
  171.         S[i].first += 10000;
  172.         S[i].second += 10000;
  173.     }
  174.             drY = B.second;
  175.         }
  176.         else if(B.first >= A2.first && B.first >= B2.first)
  177.             {
  178.                 drX = B2.first;
  179.                 drY = B2.second;
  180.             }
  181.     }
  182.     else
  183.         if(A.first <= B2.first) /// A deja e pe dreapta A2B2
  184.         {
  185.             stX = A.first;
  186.             stY = A.second;
  187.             if(B.first <= B2.first) /// deja stim ca e unde trebuie
  188.             {
  189.                 drX = B.first;
  190.                 drY = B.second;
  191.             }
  192.             else {
  193.                 drX = B2.first;
  194.                 drY = B2.second;
  195.             }
  196.         }
  197.     P1 = make_pair(stX,stY);
  198.     P2 = make_pair(drX,drY);
  199.  
  200.     if(stX != drX && stY != drY)
  201.     {
  202.         if(apartine(A,B,P1) && apartine(A2,B2,P1))
  203.             thenew[++nrn] = P1;
  204.         if(apartine(A,B,P2) && apartine(A2,B2,P2))
  205.             thenew[++nrn] = P2;
  206.         return;
  207.     }
  208.     if(apartine(A,B,P1) && apartine(A2,B2,P1))
  209.         thenew[++nrn] = make_pair(stX,stY); /// practic doar in capat s-au intersectat
  210. }
  211.  
  212.  
  213.  
  214. void GET_intersections()
  215. {
  216.     int a1,b1,c1,a2,b2,c2,cmn;
  217.     double _newx,_newy;
  218.     pair<double,double>pct;
  219.     for(int i = 1; i <= N; ++i)
  220.     {
  221.         a1 = ecA(pointsN[i],pointsN[i+1]);
  222.         b1 = ecB(pointsN[i],pointsN[i+1]);
  223.         c1 = ecC(pointsN[i],pointsN[i+1]);
  224.         cmn = _gcd(a1,_gcd(b1,c1));
  225.         a1 /= cmn;b1 /= cmn;c1 /= cmn;
  226.         if(a1 < 0) a1 *= -1, b1 *= -1, c1 *= -1;
  227.  
  228.         for(int j = 1; j <= M; ++j)
  229.         {
  230.             a2 = ecA(pointsM[j],pointsM[j+1]);
  231.             b2 = ecB(pointsM[j],pointsM[j+1]);
  232.             c2 = ecC(pointsM[j],pointsM[j+1]);
  233.             cmn = _gcd(a2,_gcd(b2,c2));
  234.             a2 /= cmn;b2 /= cmn;c2 /= cmn;
  235.             if(a2 < 0) a2 *= -1, b2 *= -1, c2 *= -1;
  236.  
  237.             if(panta(pointsN[i],pointsN[i+1] , pointsM[j],pointsM[j+1]) ){ /// aici nu stim exact ce se intampla ( trebuie sa coincida dreptele )
  238.                 if(a1 != a2 || b1 != b2 || c1 != c2)
  239.                         continue;
  240.                 baga(pointsN[i],pointsN[i+1],pointsM[j],pointsM[j+1]);
  241.             }
  242.  
  243.             _newx = (c2*b1 - c1*b2)/((double) a1*b2 - a2*b1);
  244.             _newy = (c2*a1 - c1*a2)/((double) b1*a2 - b2*a1);
  245.             pct = make_pair(_newx,_newy);
  246.             if(apartine(pointsN[i],pointsN[i+1],pct) &&
  247.                apartine(pointsM[j],pointsM[j+1],pct))
  248.                 thenew[++nrn] = pct;
  249.  
  250.         }
  251.     }
  252. }
  253.  
  254. double cross(pair<double,double> A, pair<double,double> B, pair<double,double> C)
  255. {
  256.     return A.first * B.second + B.first * C.second + C.first * A.second
  257.          - C.first * B.second - C.second * A.first - B.first * A.second;
  258. }
  259.  
  260. class cmp{
  261. public:
  262.     bool operator()(const pair<double,double> A, const pair<double,double> B)const
  263.     {
  264.        return cross(thenew[1],A,B)<0;
  265.     }
  266. };
  267.  
  268. class cmp2{
  269. public:
  270.     bool operator() (const pair<double,double> A,const pair<double,double> B)const
  271.     {
  272.         return atan2(A.second-Py,A.first-Px) < atan2(B.second-Py,B.first-Px);
  273.     }
  274. };
  275.  
  276. void sorteaza2()
  277. {
  278.     for(int i = 1; i <= nrn; ++i)
  279.         Px += thenew[i].first,Py += thenew[i].second;
  280.     Px /= nrn;
  281.     Py /= nrn;
  282.  
  283.     sort(thenew+1,thenew+nrn+1,cmp2());
  284. }
  285.  
  286.  
  287. void sorteaza()
  288. {
  289.     int pz = 1;
  290.     for(int i = 2; i <= nrn; ++i)
  291.         if(thenew[i] < thenew[pz])
  292.             pz = i;
  293.     swap(thenew[pz],thenew[1]);
  294.     sort(thenew+2,thenew+nrn+1,cmp());
  295. }
  296.  
  297. void convex_hull2()
  298. {
  299.     for(int i = 1; i <= nrn; ++i)
  300.         S[i] = thenew[i];
  301.     S[nrn+1] = S[1];
  302.     vf = nrn;
  303. }
  304. void convex_hull()
  305. {
  306.     S[1] = thenew[1];
  307.     S[2] = thenew[2];
  308.     for(int i = 3; i <= nrn; ++i)
  309.     {
  310.         while(vf >= 2 && cross(S[vf-1],S[vf],thenew[i]) > 0)
  311.             --vf;
  312.         S[++vf] = thenew[i];
  313.     }
  314. }
  315. double areaT;
  316.  
  317. double abso(double x)
  318. {
  319.     if(x > 0) return x; return -x;
  320. }
  321.  
  322. double arie(pair<double,double> A,pair<double,double> B) ///( dublul ariei )
  323. {
  324.     return (double)( abso(A.second) + abso(B.second) ) * (double)(B.first-A.first) /2;
  325. }
  326.  
  327. #include <fstream>
  328. #include <iomanip>
  329.  
  330. void get_arie()
  331. {
  332.     ofstream fout("arie.out");
  333.     S[vf+1] = S[1];
  334.     for(int i = 1; i <= vf+1; ++i)
  335.     {
  336.         S[i].first += 10000;
  337.         S[i].second += 10000;
  338.     }
  339.     for(int i = 1; i <= vf; ++i)
  340.         areaT += arie(S[i],S[i+1]);
  341.     ///printf("%.3lf\n",abso(areaT));
  342.     areaT = abso(areaT);
  343.     fout << setprecision(3) << fixed;
  344.     if(areaT > 0.002)
  345.         fout << areaT;
  346.     else
  347.         fout << "0.000";
  348. }
  349.  
  350. int main()
  351. {
  352.     freopen("arie.in","r",stdin);
  353.     freopen("arie.out","w",stdout);
  354.  
  355.     read();
  356.     GET_interiorPOINTS1();
  357.     GET_interiorPOINTS2();
  358.     GET_intersections();
  359.     sorteaza2();
  360.     convex_hull2();
  361.     get_arie();
  362.  
  363.     return 0;
  364. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement