На плоскости задано такое множество из N многоугольников, что выполняются следующие условия:
Напишите программу POLYGON, которая для каждого многоугольника выдает количество многоугольников, внутри которых он находится.
Входные данные
Первая строка входного файла содержит целое число N — количество многоугольников, 3 ≤ N≤ 10000. Следующие N строк файла описывают N многоугольников. (i+1)–ая строка файла описывает i–ый многоугольник. Первое целое число Ci — количество вершин многоугольника, 3≤ Ci≤ 20. Последующие Ci пар чисел — координаты вершин многоугольника в порядке его обхода. Координаты вершин — целые числа, принадлежащие диапазону от -2000000000 до 2000000000.
Выходные данные
Единственная строка выходного файла должна содержать N чисел: i–ое число строки должно быть Pi — количество многоугольников, внутри которых находится i–ый многоугольник.
Реализация:
Важным условием есть то что многоугольники не имеют общих точек.
1. Создадим массив размером 3хN;
2. В первый столбец занесём самую правую точку каждого многоугольника(можно "самую левую" или другую "самую" точку).
3. В второй столбец занесём номер многоугольника, так как на важна последовательность.
4. Отсортируем массив по спаданию самой правой точки.
5. Так как многоугольник точка которого лежит дальше всех не будет находиться в любом другом многоугольнику то в третий столбец заносим "0". Следующий многоугольник лежит только в одном другом многоугольнику заносим ему в третий столбец "1" и так до конца.
6. Так как нам нужно вывести в том же порядке в котором ми и получали данные то сортируем массив по втором столбу в который мы заносили номер многоугольник.
7. Выводим
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
long long a,b,c,n,mas[10011][30],mas2[10011][3];
cin>>n;
for(int i=0;i<n;i++){
cin>>mas[i][0];
for(int j=1;j<=(mas[i][0]*2);j++)
cin>>mas[i][j];
}
// Пункт №2
for(int i=0;i<=n;i++){
mas2[i][0]=mas[i][1];
for(int j=1;j<=mas[i][0]*2;j+=2){
if(mas2[i][0]<mas[i][j])
mas2[i][0]=mas[i][j];
}
}
// Пункт №3
for(int i=0;i<n;i++){mas2[i][1]=i+1;}
// Пункт №4
for(int i=0;i<n;i++)
for(int j=0;j<n-1;j++){
if(mas2[j][0]<mas2[j+1][0]){
int temp;
temp=mas2[j][0];
mas2[j][0]=mas2[j+1][0];
mas2[j+1][0]=temp;
temp=mas2[j][1];
mas2[j][1]=mas2[j+1][1];
mas2[j+1][1]=temp;
temp=mas2[j][2];
mas2[j][2]=mas2[j+1][2];
mas2[j+1][2]=temp;
}
}
// Пункт №5
for(int i=0;i<=n;i++){mas2[i][2]=i;}
// Пункт №6
for(int i=0;i<n;i++)
for(int j=0;j<n-1;j++){
if(mas2[j][1]>mas2[j+1][1]){
int temp;
temp=mas2[j][0];
mas2[j][0]=mas2[j+1][0];
mas2[j+1][0]=temp;
temp=mas2[j][1];
mas2[j][1]=mas2[j+1][1];
mas2[j+1][1]=temp;
temp=mas2[j][2];
mas2[j][2]=mas2[j+1][2];
mas2[j+1][2]=temp;
}
}
// Пункт №7
for(int i=0;i<n-1;i++)
cout<<mas2[i][2]<<" ";
cout<<mas2[n-1][2]<<endl;
}
Есть решение которого нет на сайте? Пиши admin@devexe.top