結果

問題 No.325 マンハッタン距離2
ユーザー koyumeishikoyumeishi
提出日時 2015-12-18 13:47:47
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 5,740 bytes
コンパイル時間 965 ms
コンパイル使用メモリ 88,584 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-16 08:31:10
合計ジャッジ時間 1,812 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 1 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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-7

class xy{
public:
	long double x;
	long double y;
	xy() : x(0), y(0) {}
	xy(long double xx, long 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);}
	xy operator * (const long double& k) const{return xy(this->x * k, this->y * k);}
	
	void operator += (const xy& v){x+=v.x;	y+=v.y;}
	void operator -= (const xy& v){x-=v.x;	y-=v.y;}
	void operator *= (const long double& k){x*=k;  y*=k;}

	bool operator < (const xy& v) const{
		if(x!=v.x) return x < v.x;
		return y < v.y;
	}
	bool operator > (const xy& v) const{
		if(x!=v.x) return x > v.x;
		return y > v.y;
	}
	bool operator == (const xy& v) const{
		return fabs(x-v.x) + fabs(y-v.y) < EPS;
	}
};
xy operator * (const long double& k, const xy& v){return v*k;}

//u corss v
long double cross(const xy& u, const xy& v){
	return u.x*v.y - u.y*v.x;
}

//u dot v
long double dot(const xy& u, const xy& v){
	return u.x*v.x + u.y*v.y;
}

//distance between two points
long 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
long 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) ) );
}

int ccw(xy p1, xy p2, xy p3){
	p2 -= p1;
	p3 -= p1;
	long 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;				//out of segment : p3-p1-p2
	if( dot(p3,p3) - dot(p2,p2) > EPS) return -2;	//out of segment : p1-p2-p3
	return 0; 										//on the segment : p1-p3-p2
}

//are two segment p1-p2 , p3-p4 parallel?
bool is_parallel(xy p1, xy p2, xy p3, xy p4){
	return abs(ccw(p1,p2, p3))!=1 && abs(ccw(p1,p2, p4))!=1;
}

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

bool inter_ss(const pair<xy,xy>& l1, const pair<xy,xy>& l2){
	return inter_ss(l1.first, l1.second, l2.first, l2.second);
}

//return crossing point l1 and l2 without checking
xy inter_point(const pair<xy,xy>& l1, const pair<xy,xy>& l2){
	long double a = cross(l2.second - l1.first, l2.second - l2.first);
	//long double b = cross(l1.second - l1.first, l2.second - l1.first);
	long double c = cross(l1.second - l1.first, l2.second - l2.first);
	long double lam = a/c;
	return l1.first + (l1.second - l1.first)*lam;
}

//convex_hull
//O(n log n)
vector<xy> convex_hull(vector<xy> &v){
	if(v.size() == 0){
		return {};
	}
	sort( v.begin(), v.end() );
	int k = 0;	//nums of vertex
	vector<xy> tmp(v.size()*2);
	//conect i from k
	for(int i=0; i<v.size(); i++){
		while(k>1 && cross (tmp[k-1] - tmp[k-2], v[i] - tmp[k-1]) <= 0 ) k--;
		tmp[k] = v[i];
		k++;
	}
	
	for(int i=v.size()-2, t=k; i>=0; i--){
		while(k>t && cross(tmp[k-1] - tmp[k-2], v[i] - tmp[k-1]) <= 0 ) k--;
		tmp[k] = v[i];
		k++;
	}

	tmp.resize(k-1);
	return tmp;
}

//O(n)
long double polygon_area(const vector<xy>& poly){
	long double ret = 0;
	for(int i=0; i<poly.size(); i++){
		ret += cross(poly[i], poly[(i+1)%poly.size()]);
	}
	return ret*0.5;
}
//O(n)
bool point_inner_polygon(const xy& p, const vector<xy>& poly){
	bool ret = false;
	for(int i=0; i<poly.size(); i++){
		xy high = poly[i] - p;
		xy low = poly[(i+1)%poly.size()] - p;
		if(high.y<low.y) swap(high, low);
		if(high.y>=0 && low.y < 0){
			if(cross(low,high) > 0) ret = !ret;
		}
		if(fabs(cross(low,high)) < EPS && dot(high,low)<EPS){
			return true; //on the segment
		}
	}
	return ret;
}

ostream& operator << (ostream& os, xy& p){
	os << "{" << p.x << ", " << p.y << "}";
	return os;
}
template<class T>
ostream& operator << (ostream& os, vector<T> vec){
	for(int i=0; i<vec.size(); i++){
		os << vec[i] << " ";
	}
	return os;
}
template<class T> istream& operator , (istream& is, T& val){is >> val; return is;}

#include <cassert>
int main(){
	long long x1,y1,x2,y2, d;
	cin >> x1,y1,x2,y2,d;


	vector<xy> rho = {xy(0,d), xy(d,0), xy(0,-d), xy(-d,0)};
	vector<xy> rec = {xy(x1,y1), xy(x1,y2), xy(x2,y2), xy(x2,y1)};

	if(d==0){
		cout << (point_inner_polygon(xy(0,0), rec)?1:0) << endl;
		return 0;
	}

	vector<xy> p;
	for(int i=0; i<rho.size(); i++){
		for(int j=0; j<rec.size(); j++){
			if(inter_ss(rho[i],rho[(i+1)%rho.size()], rec[j], rec[(j+1)%rec.size()])){
				if(is_parallel(rho[i],rho[(i+1)%rho.size()], rec[j], rec[(j+1)%rec.size()]) == false){
					p.push_back( inter_point({rho[i],rho[(i+1)%rho.size()]}, {rec[j], rec[(j+1)%rec.size()]}) );
				}
			}
		}
	}
	for(int j=0; j<rec.size(); j++){
		if(point_inner_polygon(rec[j], rho)){
			p.push_back(rec[j]);
		}
	}

	for(int i=0; i<rho.size(); i++){
		if(point_inner_polygon(rho[i], rec)){
			p.push_back(rho[i]);
		}
	}
	sort(p.begin(), p.end());
	p.erase( unique(p.begin(), p.end()), p.end());

	//cerr << p << endl;

	if(p.size()<=1){
		cout << p.size() << endl;
		return 0;
	}

	vector<xy> hull = convex_hull(p);

	long double s = polygon_area(hull);

	long long lattice_b = 0;
	for(int i=0; i<hull.size(); i++){
		xy tmp = hull[i]-hull[(i+1)%hull.size()];
		lattice_b += max(fabs(tmp.x), fabs(tmp.y)) + EPS;
	}
	long long lattice_i = (s - lattice_b/2 + 1) + EPS;

	long long ans = lattice_b + lattice_i;
	cout << ans << endl;
	return 0;
}
0