#17140 (C++11) No.172 UFOを捕まえろ

• 問題: No.172 UFOを捕まえろ
• ユーザー: koyumeishi
• 提出日時: 2015-03-27 00:04:55
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 10 ms / 5,000 ms
• コード長: 2,455 bytes
• コンパイル時間: 1,125 ms
• コンパイル使用メモリ: 77,644 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-15 14:01:28
• 合計ジャッジ時間: 1,693 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	10 ms; 5,248 KB
testcase_01	AC	10 ms; 5,248 KB
testcase_02	AC	10 ms; 5,248 KB
testcase_03	AC	10 ms; 5,248 KB
testcase_04	AC	10 ms; 5,248 KB
testcase_05	AC	9 ms; 5,248 KB
testcase_06	AC	10 ms; 5,248 KB
testcase_07	AC	10 ms; 5,248 KB
testcase_08	AC	9 ms; 5,248 KB
testcase_09	AC	10 ms; 5,248 KB
testcase_10	AC	10 ms; 5,248 KB
testcase_11	AC	9 ms; 5,248 KB
testcase_12	AC	9 ms; 5,248 KB
testcase_13	AC	9 ms; 5,248 KB
testcase_14	AC	9 ms; 5,248 KB
testcase_15	AC	9 ms; 5,248 KB
testcase_16	AC	9 ms; 5,248 KB
testcase_17	AC	9 ms; 5,248 KB
testcase_18	AC	10 ms; 5,248 KB
testcase_19	AC	9 ms; 5,248 KB
testcase_20	AC	10 ms; 5,248 KB
testcase_21	AC	9 ms; 5,248 KB
testcase_22	AC	10 ms; 5,248 KB
testcase_23	AC	10 ms; 5,248 KB

ソースコード

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

#define EPS 1e-6

class xy{
	
public:
	double x;
	double y;

	xy(){

	}
	
	xy(double xx, double yy){
		x = xx;
		y = yy;
	}

	xy(const xy &v){
		x = v.x;
		y = v.y;
	}

	xy& operator=(const xy &v){
		x = v.x;
		y = v.y;
		return *this;
	}

	xy operator+(const xy &v) const{
		return xy(this->x+v.x, this->y+v.y);
		
	}
	
	xy operator-(const xy &v) const{
		return xy(this->x-v.x, this->y-v.y);
	}
	
	void operator+=(const xy &v){
		x+=v.x;
		y+=v.y;
	}
	void operator-=(const xy &v){
		x-=v.x;
		y-=v.y;
	}
};
//for sorting
bool comp_xy(const xy &a, const xy &b){
	if(a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

//u,v : vector O = (0,0)
double cross(const xy &u, const xy &v){
	return u.x*v.y - u.y*v.x;
}

//u,v : vector O = (0,0)
double dot(const xy &u, const xy &v){
	return u.x*v.x + u.y*v.y;
}

//distance between two points
double dist_p_p(const xy &a, const xy &b){
	return sqrt( fabs(dot(a-b, a-b)) );
}

//distance between a point and a line segment
double dist_p_ls(const xy &p, const xy &s1, const xy &s2){
	xy vl = s2 - s1;
	xy vp = p - s1;

	return fabs( cross(vl, vp) / sqrt( dot(vl, vl) ) );
}

//zero -> p1
int ccw(xy p1, xy p2, xy p3){
	p2 -= p1;
	p3 -= p1;
	double c = cross(p2,p3);
	if( c > EPS /* c > 0 */) return +1;			//counter-clockwise
	if( c < -EPS /* c < 0 */) return -1;		//clock-wise
	if( dot(p2,p3) < -EPS) return +2;			//on segment : p3-p1-p2
	if( dot(p3,p3) < dot(p2,p2) +EPS ) return -2;	//on segment : p1-p3-p2
	return 0;
}

//segment p1-p2, p3-p4
bool inter_ss(xy p1, xy p2, xy p3, xy p4){
	return ( (ccw(p1,p2, p3) * ccw(p1,p2, p4) <= 0) && (ccw(p3,p4, p1) * ccw(p3,p4, p2) <= 0 ) ) ;
}

int main(){
	int x,y,r;
	cin >> x >> y >> r;

	int ans = -1;
	for(int i=100000; i>=1; i--){
		bool ok = true;

		vector<int> dx = {i,0,-i,0};
		vector<int> dy = {0,i,0,-i};
		for(int j=0; j<4; j++){
			double dist = dist_p_ls(xy(x,y), xy(dx[j],dy[j]) , xy(dx[(j+1)%4],dy[(j+1)%4]));


			dist = min( {dist, 
				dist_p_p( xy(x,y), xy(dx[j],dy[j]) ), 
				dist_p_p( xy(x,y), xy(dx[(j+1)%4],dy[(j+1)%4]) )
			} );


			if(dist < r + EPS) ok = false;

			int ccw_ = ccw(xy(dx[j],dy[j]), xy(dx[(j+1)%4],dy[(j+1)%4]), xy(x,y));

			if( ccw_ != 1 ) ok = false;
		}

		if(ok){
			ans = i;
		}
	}

	cout << ans << endl;
	return 0;
}