Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <iomanip>
- #include <algorithm>
- #include <fstream>
- using namespace std;
- ifstream fin("arie.in");
- ofstream fout("arie.out");
- const int N = 20;
- struct punct{
- double x, y;
- };
- punct poli1[N+1], poli2[N+1];
- punct newPoli[N*N+1];
- bool remove1[N+1], remove2[N+1];
- double area1, area2, bigArea, outsideArea;
- vector <punct> addPoints;
- vector <punct> bigPoli;
- double getAreaTriangle(punct P1, punct P2, punct P3){
- double area = (P1.x * (P2.y - P3.y) - P2.x * (P1.y - P3.y) + P3.x * (P1.y - P2.y)) / 2;
- return area;
- }
- double getAreaPoli(punct coords[], int points, punct center){
- double area = 0;
- for(int i=1; i<=points; i++)
- area += abs(getAreaTriangle(coords[i-1], coords[i], center));
- return area;
- }
- pair <double, double> getLineEq(punct A, punct B){
- double m = (A.y - B.y) / (A.x - B.x);
- double n = A.y - m * A.x;
- return make_pair(m, n);
- }
- pair <double, double> intersect(pair <double, double> d1, pair<double, double> d2){
- double x = (d2.second - d1.second) / (d1.first - d2.first);
- double y = d1.first * x + d1.second;
- return make_pair(x, y);
- }
- bool vertical(punct A, punct B){
- if(A.x - B.x == 0)
- return true;
- return false;
- }
- void addIntersections(punct A1, punct B1, punct A2, punct B2){
- punct C;
- pair <double, double> d1, d2;
- if(vertical(A1, B1) && vertical(A2, B2))
- return;
- if(vertical(A1, B1)){
- d2 = getLineEq(A2, B2);
- C.x = A1.x;
- C.y = d2.first * C.x + d2.second;
- }
- else if(vertical(A2, B2)){
- d1 = getLineEq(A1, B1);
- C.x = A2.x;
- C.y = d1.first * C.x + d1.second;
- }
- else{
- d1 = getLineEq(A1, B1), d2 = getLineEq(A2, B2);
- if(d1.first == d2.first)
- return;
- C.x = intersect(d1, d2).first, C.y = intersect(d1, d2).second;
- }
- int x_min = min(min(A1.x, B1.x), min(A2.x, B2.x));
- int y_min = min(min(A1.y, B1.y), min(A2.y, B2.y));
- int x_max = max(max(A1.x, B1.x), max(A2.x, B2.x));
- int y_max = max(max(A1.y, B1.y), max(A2.y, B2.y));
- if((x_min <= C.x && C.x <= x_max) && (y_min <= C.y && C.y <= y_max))
- addPoints.push_back(C);
- }
- bool insidePoli(punct coords[], int points, punct A, int indexPoli){
- double new_area = getAreaPoli(coords, points, A);
- if(indexPoli == 1 && new_area <= area1)
- return true;
- if(indexPoli == 2 && new_area <= area2)
- return true;
- return false;
- }
- bool cmp(punct a, punct b){
- if(a.y < b.y)
- return true;
- if(a.y == b.y && a.x < b.x)
- return true;
- return false;
- }
- vector <punct> stiva1;
- vector <punct> stiva2;
- int main()
- {
- int n,m,i,j;
- punct center1, center2;
- punct up1, down1, up2, down2;
- double area;
- fin >> n;
- fin >> poli1[0].x >> poli1[0].y;
- for(i=1; i<n; i++)
- fin >> poli1[i].x >> poli1[i].y;
- fin >> m;
- fin >> poli2[0].x >> poli2[0].y;
- for(i=1; i<m; i++)
- fin >> poli2[i].x >> poli2[i].y;
- poli1[n] = poli1[0];
- poli2[m] = poli2[0];
- area1 = getAreaPoli(poli1, n, poli1[0]);
- area2 = getAreaPoli(poli2, m, poli2[0]);
- cout << area1 << " " << area2 << endl;
- for(i=1; i<=n; i++)
- for(j=1; j<=m; j++)
- addIntersections(poli1[i-1], poli1[i], poli2[j-1], poli2[j]);
- for(i=1; i<=n; i++)
- remove1[i] = insidePoli(poli2, m, poli1[i], 2);
- for(i=1; i<=m; i++)
- remove2[i] = insidePoli(poli1, n, poli2[i], 1);
- for(i=1; i<=n; i++){
- if(remove1[i] == false)
- bigPoli.push_back(poli1[i]);
- else
- cout << "Removed point " << poli1[i].x << " " << poli1[i].y << endl;
- }
- for(i=1; i<=m; i++){
- if(remove2[i] == false)
- bigPoli.push_back(poli2[i]);
- else
- cout << "Removed point " << poli2[i].x << " " << poli2[i].y << endl;
- }
- fout << setprecision(3) << fixed;
- if(addPoints.empty())
- fout << "0";
- else{
- while(!addPoints.empty()){
- bigPoli.push_back(addPoints.back());
- addPoints.pop_back();
- }
- sort(bigPoli.begin(), bigPoli.end(), cmp);
- stiva1.push_back(bigPoli[0]);
- stiva2.push_back(bigPoli[0]);
- n = (int)bigPoli.size();
- for(i=1; i<n; i++){
- if(bigPoli[i].x == bigPoli[i-1].x && bigPoli[i].y == bigPoli[i-1].y)
- continue;
- area = getAreaTriangle(bigPoli[0], bigPoli[n-1], bigPoli[i]);
- if(area <= 0){
- int top2 = (int)stiva2.size();
- while(top2 > 1 && getAreaTriangle(stiva2[top2-2], stiva2[top2-1], bigPoli[i]) < 0){
- cout << "DREAPTA Intre punctele (" << stiva2[top2-2].x << " " << stiva2[top2-2].y << ") ";
- cout << "(" << stiva2[top2-1].x << " " << stiva2[top2-1].y << ") ";
- cout << "(" << bigPoli[i].x << " " << bigPoli[i].y << ") avem outside area = ";
- outsideArea += abs(getAreaTriangle(stiva2[top2-2], stiva2[top2-1], bigPoli[i]));
- cout << abs(getAreaTriangle(stiva2[top2-2], stiva2[top2-1], bigPoli[i])) << endl;
- stiva2.pop_back();
- top2--;
- }
- stiva2.push_back(bigPoli[i]);
- }
- if(area >= 0){
- int top1 = (int)stiva1.size();
- while(top1 > 1 && getAreaTriangle(stiva1[top1-2], stiva1[top1-1], bigPoli[i]) > 0){
- cout << "STANGA Intre punctele (" << stiva1[top1-2].x << " " << stiva1[top1-2].y << ") ";
- cout << "(" << stiva2[top1-1].x << " " << stiva2[top1-1].y << ") ";
- cout << "(" << bigPoli[i].x << " " << bigPoli[i].y << ") avem outside area = ";
- outsideArea += abs(getAreaTriangle(stiva1[top1-2], stiva1[top1-1], bigPoli[i]));
- cout << abs(getAreaTriangle(stiva1[top1-2], stiva1[top1-1], bigPoli[i])) << endl;
- stiva1.pop_back();
- top1--;
- }
- stiva1.push_back(bigPoli[i]);
- }
- }
- int pun = 0;
- int top1 = (int)stiva1.size();
- int top2 = (int)stiva2.size();
- up1 = stiva2[0], down1 = stiva2[0];
- for(i=0; i<top2; i++){
- newPoli[pun++] = stiva2[i];
- if(stiva2[i].y > up1.y)
- up1 = stiva2[i];
- if(stiva2[i].y < down1.y)
- down1 = stiva2[i];
- }
- for(i=top1 - 2; i>0; i--){
- newPoli[pun++] = stiva1[i];
- if(stiva1[i].y > up1.y)
- up1 = stiva1[i];
- if(stiva1[i].y < down1.y)
- down1 = stiva1[i];
- }
- for(i=0; i<pun; i++)
- cout << newPoli[i].x << " " << newPoli[i].y << endl;
- newPoli[pun++] = newPoli[0];
- center1.x = (up1.x + down1.x) / 2;
- center1.y = (up1.y + down1.y) / 2;
- cout << "cut " << outsideArea << endl;
- bigArea = getAreaPoli(newPoli, pun, newPoli[0]);
- cout << "bigArea " << bigArea << endl;
- fout << area1 + area2 - (bigArea - outsideArea);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement