Решение задачи Одинаковые прямоугольники с Codeforces

Без пояснения   Просмотров: 1645

Вам задано 4n палочек, длина i-й палочки равна ai.

Вам необходимо составить n прямоугольников, каждый из которых будет состоять ровно из 4 палочек из заданного набора. Прямоугольник имеет четыре стороны, противоположные стороны должны иметь одинаковые длины и все углы в нем должны быть прямые. Заметьте, что каждая палочка может быть использована только в одном прямоугольнике. Каждая палочка должна быть использована как сторона, вы не можете ломать палочки или использовать не ее полную длину.

Вы хотите, чтобы все прямоугольники имели одинаковую площадь. Площадь прямоугольника со сторонами a и b равна a⋅b.

Ваша задача — сказать, возможно ли составить ровно n прямоугольников одинаковой площади или нет.

Вам необходимо ответить на q независимых запросов.

Код 

#include<bits/stdc++.h>
using namespace std;
int q,n,a[500],m,f;
int main()
{
	cin>>q;
	while(q--)
	{
		cin>>n;
		f=0;
		for(int i=0;i<4*n;i++)
			cin>>a[i];
		sort(a,a+4*n);
		for(int i=0;i<2*n;i++)
			if(a[2*i]!=a[2*i+1])
				f=1;
		m=a[0]*a[4*n-1];
		for(int i=0;i<n;i++)
			if(a[2*i]*a[4*n-2*i-1]!=m)
				f=1;
		if(f)
			cout<<"NO"<<endl;
		else
			cout<<"YES"<<endl;
	}
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp