結果

問題 No.172 UFOを捕まえろ
コンテスト
ユーザー koyumeishi
提出日時 2015-03-27 00:04:55
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0