Advertisement
Guest User

Untitled

a guest
Feb 28th, 2020
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iomanip>
  5. #include <algorithm>
  6. #include <fstream>
  7. using namespace std;
  8.  
  9. ifstream fin("arie.in");
  10. ofstream fout("arie.out");
  11.  
  12. const int N = 20;
  13.  
  14. struct punct{
  15.     double x, y;
  16. };
  17.  
  18. punct poli1[N+1], poli2[N+1];
  19. punct newPoli[N*N+1];
  20. bool remove1[N+1], remove2[N+1];
  21. double area1, area2, bigArea, outsideArea;
  22. vector <punct> addPoints;
  23. vector <punct> bigPoli;
  24.  
  25. double getAreaTriangle(punct P1, punct P2, punct P3){
  26.     double area = (P1.x * (P2.y - P3.y) - P2.x * (P1.y - P3.y) + P3.x * (P1.y - P2.y)) / 2;
  27.     return area;
  28. }
  29.  
  30. double getAreaPoli(punct coords[], int points, punct center){
  31.     double area = 0;
  32.     for(int i=1; i<=points; i++)
  33.         area += abs(getAreaTriangle(coords[i-1], coords[i], center));
  34.     return area;
  35. }
  36.  
  37. pair <double, double> getLineEq(punct A, punct B){
  38.     double m = (A.y - B.y) / (A.x - B.x);
  39.     double n = A.y - m * A.x;
  40.     return make_pair(m, n);
  41. }
  42.  
  43. pair <double, double> intersect(pair <double, double> d1, pair<double, double> d2){
  44.     double x = (d2.second - d1.second) / (d1.first - d2.first);
  45.     double y = d1.first * x + d1.second;
  46.     return make_pair(x, y);
  47. }
  48.  
  49. bool vertical(punct A, punct B){
  50.     if(A.x - B.x == 0)
  51.         return true;
  52.     return false;
  53. }
  54.  
  55. void addIntersections(punct A1, punct B1, punct A2, punct B2){
  56.     punct C;
  57.     pair <double, double> d1, d2;
  58.     if(vertical(A1, B1) && vertical(A2, B2))
  59.         return;
  60.     if(vertical(A1, B1)){
  61.         d2 = getLineEq(A2, B2);
  62.         C.x = A1.x;
  63.         C.y = d2.first * C.x + d2.second;
  64.     }
  65.     else if(vertical(A2, B2)){
  66.         d1 = getLineEq(A1, B1);
  67.         C.x = A2.x;
  68.         C.y = d1.first * C.x + d1.second;
  69.     }
  70.     else{
  71.         d1 = getLineEq(A1, B1), d2 = getLineEq(A2, B2);
  72.  
  73.         if(d1.first == d2.first)
  74.             return;
  75.         C.x = intersect(d1, d2).first, C.y = intersect(d1, d2).second;
  76.     }
  77.     int x_min = min(min(A1.x, B1.x), min(A2.x, B2.x));
  78.     int y_min = min(min(A1.y, B1.y), min(A2.y, B2.y));
  79.     int x_max = max(max(A1.x, B1.x), max(A2.x, B2.x));
  80.     int y_max = max(max(A1.y, B1.y), max(A2.y, B2.y));
  81.     if((x_min <= C.x && C.x <= x_max) && (y_min <= C.y && C.y <= y_max))
  82.         addPoints.push_back(C);
  83. }
  84.  
  85. bool insidePoli(punct coords[], int points, punct A, int indexPoli){
  86.     double new_area = getAreaPoli(coords, points, A);
  87.     if(indexPoli == 1 && new_area <= area1)
  88.         return true;
  89.     if(indexPoli == 2 && new_area <= area2)
  90.         return true;
  91.     return false;
  92. }
  93.  
  94. bool cmp(punct a, punct b){
  95.     if(a.y < b.y)
  96.         return true;
  97.     if(a.y == b.y && a.x < b.x)
  98.         return true;
  99.     return false;
  100. }
  101.  
  102. vector <punct> stiva1;
  103. vector <punct> stiva2;
  104.  
  105. int main()
  106. {
  107.     int n,m,i,j;
  108.     punct center1, center2;
  109.     punct up1, down1, up2, down2;
  110.     double area;
  111.  
  112.     fin >> n;
  113.     fin >> poli1[0].x >> poli1[0].y;
  114.     for(i=1; i<n; i++)
  115.         fin >> poli1[i].x >> poli1[i].y;
  116.     fin >> m;
  117.     fin >> poli2[0].x >> poli2[0].y;
  118.     for(i=1; i<m; i++)
  119.         fin >> poli2[i].x >> poli2[i].y;
  120.  
  121.     poli1[n] = poli1[0];
  122.     poli2[m] = poli2[0];
  123.  
  124.     area1 = getAreaPoli(poli1, n, poli1[0]);
  125.     area2 = getAreaPoli(poli2, m, poli2[0]);
  126.     cout << area1 << " " << area2 << endl;
  127.  
  128.     for(i=1; i<=n; i++)
  129.         for(j=1; j<=m; j++)
  130.             addIntersections(poli1[i-1], poli1[i], poli2[j-1], poli2[j]);
  131.  
  132.     for(i=1; i<=n; i++)
  133.         remove1[i] = insidePoli(poli2, m, poli1[i], 2);
  134.     for(i=1; i<=m; i++)
  135.         remove2[i] = insidePoli(poli1, n, poli2[i], 1);
  136.  
  137.     for(i=1; i<=n; i++){
  138.         if(remove1[i] == false)
  139.             bigPoli.push_back(poli1[i]);
  140.         else
  141.             cout << "Removed point " << poli1[i].x << " " << poli1[i].y << endl;
  142.     }
  143.     for(i=1; i<=m; i++){
  144.         if(remove2[i] == false)
  145.             bigPoli.push_back(poli2[i]);
  146.         else
  147.             cout << "Removed point " << poli2[i].x << " " << poli2[i].y << endl;
  148.     }
  149.  
  150.     fout << setprecision(3) << fixed;
  151.  
  152.     if(addPoints.empty())
  153.         fout << "0";
  154.     else{
  155.         while(!addPoints.empty()){
  156.             bigPoli.push_back(addPoints.back());
  157.             addPoints.pop_back();
  158.         }
  159.         sort(bigPoli.begin(), bigPoli.end(), cmp);
  160.  
  161.         stiva1.push_back(bigPoli[0]);
  162.         stiva2.push_back(bigPoli[0]);
  163.         n = (int)bigPoli.size();
  164.         for(i=1; i<n; i++){
  165.             if(bigPoli[i].x == bigPoli[i-1].x && bigPoli[i].y == bigPoli[i-1].y)
  166.                 continue;
  167.             area = getAreaTriangle(bigPoli[0], bigPoli[n-1], bigPoli[i]);
  168.             if(area <= 0){
  169.                 int top2 = (int)stiva2.size();
  170.                 while(top2 > 1 && getAreaTriangle(stiva2[top2-2], stiva2[top2-1], bigPoli[i]) < 0){
  171.                     cout << "DREAPTA Intre punctele (" << stiva2[top2-2].x << " " << stiva2[top2-2].y << ")   ";
  172.                     cout << "(" << stiva2[top2-1].x << " " << stiva2[top2-1].y << ")   ";
  173.                     cout << "(" << bigPoli[i].x << " " << bigPoli[i].y << ") avem outside area = ";
  174.                     outsideArea += abs(getAreaTriangle(stiva2[top2-2], stiva2[top2-1], bigPoli[i]));
  175.                     cout << abs(getAreaTriangle(stiva2[top2-2], stiva2[top2-1], bigPoli[i])) << endl;
  176.                     stiva2.pop_back();
  177.                     top2--;
  178.                 }
  179.                 stiva2.push_back(bigPoli[i]);
  180.             }
  181.             if(area >= 0){
  182.                 int top1 = (int)stiva1.size();
  183.                 while(top1 > 1 && getAreaTriangle(stiva1[top1-2], stiva1[top1-1], bigPoli[i]) > 0){
  184.                     cout << "STANGA Intre punctele (" << stiva1[top1-2].x << " " << stiva1[top1-2].y << ")   ";
  185.                     cout << "(" << stiva2[top1-1].x << " " << stiva2[top1-1].y << ")   ";
  186.                     cout << "(" << bigPoli[i].x << " " << bigPoli[i].y << ") avem outside area = ";
  187.                     outsideArea += abs(getAreaTriangle(stiva1[top1-2], stiva1[top1-1], bigPoli[i]));
  188.                     cout << abs(getAreaTriangle(stiva1[top1-2], stiva1[top1-1], bigPoli[i])) << endl;
  189.                     stiva1.pop_back();
  190.                     top1--;
  191.                 }
  192.                 stiva1.push_back(bigPoli[i]);
  193.             }
  194.         }
  195.         int pun = 0;
  196.         int top1 = (int)stiva1.size();
  197.         int top2 = (int)stiva2.size();
  198.         up1 = stiva2[0], down1 = stiva2[0];
  199.         for(i=0; i<top2; i++){
  200.             newPoli[pun++] = stiva2[i];
  201.             if(stiva2[i].y > up1.y)
  202.                 up1 = stiva2[i];
  203.             if(stiva2[i].y < down1.y)
  204.                 down1 = stiva2[i];
  205.         }
  206.         for(i=top1 - 2; i>0; i--){
  207.             newPoli[pun++] = stiva1[i];
  208.             if(stiva1[i].y > up1.y)
  209.                 up1 = stiva1[i];
  210.             if(stiva1[i].y < down1.y)
  211.                 down1 = stiva1[i];
  212.         }
  213.  
  214.         for(i=0; i<pun; i++)
  215.             cout << newPoli[i].x << " " << newPoli[i].y << endl;
  216.         newPoli[pun++] = newPoli[0];
  217.         center1.x = (up1.x + down1.x) / 2;
  218.         center1.y = (up1.y + down1.y) / 2;
  219.         cout << "cut " << outsideArea << endl;
  220.         bigArea = getAreaPoli(newPoli, pun, newPoli[0]);
  221.         cout << "bigArea " << bigArea << endl;
  222.         fout << area1 + area2 - (bigArea - outsideArea);
  223.     }
  224.     return 0;
  225. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement