#66776 (C++11) No.325 マンハッタン距離2

• 問題: No.325 マンハッタン距離2
• ユーザー: koyumeishi
• 提出日時: 2015-12-18 13:47:47
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 2 ms / 1,000 ms
• コード長: 5,740 bytes
• コンパイル時間: 983 ms
• コンパイル使用メモリ: 88,092 KB
• 実行使用メモリ: 4,352 KB
• 最終ジャッジ日時: 2023-10-14 13:51:06
• 合計ジャッジ時間: 2,143 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	1 ms; 4,352 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	2 ms; 4,352 KB
testcase_04	AC	1 ms; 4,348 KB
testcase_05	AC	1 ms; 4,348 KB
testcase_06	AC	1 ms; 4,348 KB
testcase_07	AC	2 ms; 4,352 KB
testcase_08	AC	1 ms; 4,352 KB
testcase_09	AC	2 ms; 4,348 KB
testcase_10	AC	2 ms; 4,352 KB
testcase_11	AC	2 ms; 4,352 KB
testcase_12	AC	2 ms; 4,348 KB
testcase_13	AC	2 ms; 4,348 KB
testcase_14	AC	2 ms; 4,348 KB
testcase_15	AC	2 ms; 4,352 KB
testcase_16	AC	2 ms; 4,348 KB
testcase_17	AC	1 ms; 4,348 KB
testcase_18	AC	2 ms; 4,348 KB
testcase_19	AC	1 ms; 4,352 KB
testcase_20	AC	1 ms; 4,352 KB
testcase_21	AC	2 ms; 4,352 KB
testcase_22	AC	2 ms; 4,348 KB
testcase_23	AC	2 ms; 4,348 KB
testcase_24	AC	2 ms; 4,352 KB
testcase_25	AC	2 ms; 4,348 KB
testcase_26	AC	2 ms; 4,352 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-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;
}