#30471 (C++11) No.55 正方形を描くだけの簡単なお仕事です。

• 問題: No.55 正方形を描くだけの簡単なお仕事です。
• ユーザー: btk
• 提出日時: 2015-06-02 15:06:39
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 50 ms / 5,000 ms
• コード長: 1,839 bytes
• コンパイル時間: 822 ms
• コンパイル使用メモリ: 92,172 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-26 22:13:03
• 合計ジャッジ時間: 2,540 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	25 ms; 5,248 KB
testcase_01	AC	46 ms; 5,376 KB
testcase_02	AC	26 ms; 5,376 KB
testcase_03	AC	26 ms; 5,376 KB
testcase_04	AC	47 ms; 5,376 KB
testcase_05	AC	47 ms; 5,376 KB
testcase_06	AC	48 ms; 5,376 KB
testcase_07	AC	50 ms; 5,376 KB
testcase_08	AC	49 ms; 5,376 KB
testcase_09	AC	48 ms; 5,376 KB
testcase_10	AC	49 ms; 5,376 KB
testcase_11	AC	15 ms; 5,376 KB
testcase_12	AC	47 ms; 5,376 KB
testcase_13	AC	37 ms; 5,376 KB
testcase_14	AC	25 ms; 5,376 KB
testcase_15	AC	48 ms; 5,376 KB
testcase_16	AC	25 ms; 5,376 KB
testcase_17	AC	43 ms; 5,376 KB
testcase_18	AC	14 ms; 5,376 KB
testcase_19	AC	49 ms; 5,376 KB
testcase_20	AC	25 ms; 5,376 KB
testcase_21	AC	24 ms; 5,376 KB
testcase_22	AC	48 ms; 5,376 KB
testcase_23	AC	31 ms; 5,376 KB
testcase_24	AC	13 ms; 5,376 KB

ソースコード

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>

using namespace std;

typedef complex<double> P;
typedef vector<P> Poly;

const double eps = 1e-8;


inline double dot(const P a, const  P b){//A dot B
	return a.real()*b.real() + a.imag()*b.imag();
}

inline double cross(const P a, const P b){//A cross B
	return a.real()*b.imag() - a.imag()*b.real();
}

bool less_P(const P& l, const P& r){
	if (l.real() == r.real())
		return l.imag() < r.imag();
	else return l.real() < r.real();
}

inline void convex_hull(Poly p, Poly& res){
	int k = 0, t;
	res.resize(2 * p.size());
	sort(p.begin(),p.end(),less_P);
	for(int i=0;i<(int)p.size();i++){
		while (k > 1 && (cross(res[k - 1] - res[k - 2], p[i] - res[k - 1])<eps))k--;
		res[k++] = p[i];
	}
	t = k;
	for(int i=(int)p.size()-1;i>=0;i--){
		while (k > t && (cross(res[k - 1] - res[k - 2], p[i] - res[k - 1])<eps))k--;
		res[k++] = p[i];
	}
	res.resize(k-1);
}


int main(){
	int x[4],y[4];
	for(int i=0;i<3;i++){
		cin>>x[i]>>y[i];
	}
	for(x[3]=-200;x[3]<=200;x[3]++)
		for(y[3]=-200;y[3]<=200;y[3]++){
			Poly test(4),res;
			for(int i=0;i<4;i++){
				test[i].real(x[i]);
				test[i].imag(y[i]);
			}
			convex_hull(test,res);
			bool flag=true;
			for(int i=0;i<(int)res.size();i++){
				double tmp=dot(res[(i+2)%res.size()]-res[(i+1)%res.size()],res[(i+1)%res.size()]-res[i]);
				if(tmp>eps||tmp<-eps)flag=false;
				tmp=abs(res[(i+2)%res.size()]-res[(i+1)%res.size()])-abs(res[(i+1)%res.size()]-res[i]);
				if(tmp>eps||tmp<-eps)flag=false;
			}
			if(flag){
				cout<<x[3]<<" "<<y[3]<<endl;
				return 0;
			}
		}
	cout<<-1<<endl;
	return 0;
}