acmicpc.net 12781(벡터, 기하), 1708(볼록 껍질, 기하), 9240(볼록 껍질, 기하)

https://www.acmicpc.net/problem/12781

종만북에서 소스를 가져왔다. 벡터로 선분이 평행한지 조사해서 평행하면 0, 아니면 4조각으로

자를 수 있다는 뜻이므로 1을 리턴했다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const double PI = 2.0 * acos(0.0);

struct vector2 {
	double x, y;
	vector2(double x_ = 0, double y_ = 0) : x(x_), y(y_) {}

	// 두 벡터가 같은 경우
	bool operator == (const vector2& rhs) const { return x == rhs.x && y == rhs.y; }

	// 벡터의 덧셈과 뺄셈, 단항 연산자의 구현
	vector2 operator + (const vector2& rhs) const { return vector2(x + rhs.x, y + rhs.y); }
	vector2 operator - (const vector2& rhs) const { return vector2(x - rhs.x, y - rhs.y); }
	vector2 operator - () const { return vector2(-x, -y); }
	bool operator < (const vector2& rhs) const 
    {
        return x != rhs.x? x < rhs.x: y < rhs.y;
    }
	// 스칼라로 곱셈
	vector2 operator * (double rhs) const { return vector2(x * rhs, y * rhs); }

	// 벡터의 길이를 반환한다
	double norm() const { return hypot(x, y); }

	// 방향이 같은 단위 벡터 (unit vector) 를 반환한다
	vector2 normalize() const { double n = norm(); return vector2(x / n, y / n); }

	// 내적/외적의 구현
	double dot(const vector2& rhs) const { return x * rhs.x + y * rhs.y; }
	double cross(const vector2& rhs) const { return x * rhs.y - rhs.x * y; }

	// 이 벡터를 rhs 에 사영한 결과
	vector2 project(const vector2& rhs) const {
		vector2 r = rhs.normalize();
		return r * r.dot(*this);
	}
};

bool inBoundingRectangle(vector2 p,vector2 a,vector2 b){
    if (b < a) swap(a,b); 
    return p == a || p == b || (a < p && p < b);  
}
 
const double EPSILON = 1e-9;
bool lineIntersection(vector2 a,vector2 b,vector2 c,vector2 d,vector2 &x){ //두직선의 교차점을 계산하는함수
    double det = (b-a).cross(d-c);  
    if (fabs(det) < EPSILON) return false; 
    x = a+(b-a)*((c-a).cross(d-c)/det);  
    return true; 
}
 
bool segmentIntersection(vector2 a,vector2 b,vector2 c,vector2 d,vector2 &p){ //a,b선분과 c,d선분의 교점을 p로 반환
    if (!lineIntersection(a,b,c,d,p)) return false; // 평행인 경우 예외처리  
    return inBoundingRectangle(p,a,b)&&inBoundingRectangle(p,c,d); 
}

int main() 
{
	vector<vector2> vec;
	for(int i=0;i<4;i++)
	{
		int x,y;
		cin>>x>>y;
		vec.push_back(vector2(x,y));
	}
	vector2 ret;
    if (!segmentIntersection(vec[0],vec[1],vec[2],vec[3],ret))
		cout<<"0\n";
    else 
		cout<<"1\n";

	return 0;
}

https://www.acmicpc.net/problem/1708

기하 파트에서 가장 기본적인 알고리즘중 하나인 볼록 껍질 구하는 문제. 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const double PI = 2.0 * acos(0.0);

struct vector2 {
	double x, y;
	vector2(double x_ = 0, double y_ = 0) : x(x_), y(y_) {}

	// 두 벡터가 같은 경우
	bool operator == (const vector2& rhs) const { return x == rhs.x && y == rhs.y; }

	// 벡터의 덧셈과 뺄셈, 단항 연산자의 구현
	vector2 operator + (const vector2& rhs) const { return vector2(x + rhs.x, y + rhs.y); }
	vector2 operator - (const vector2& rhs) const { return vector2(x - rhs.x, y - rhs.y); }
	vector2 operator - () const { return vector2(-x, -y); }
	bool operator < (const vector2& rhs) const 
    {
        return x != rhs.x? x < rhs.x: y < rhs.y;
    }
	// 스칼라로 곱셈
	vector2 operator * (double rhs) const { return vector2(x * rhs, y * rhs); }

	// 벡터의 길이를 반환한다
	double norm() const { return hypot(x, y); }

	// 방향이 같은 단위 벡터 (unit vector) 를 반환한다
	vector2 normalize() const { double n = norm(); return vector2(x / n, y / n); }

	// 내적/외적의 구현
	double dot(const vector2& rhs) const { return x * rhs.x + y * rhs.y; }
	double cross(const vector2& rhs) const { return x * rhs.y - rhs.x * y; }

	// 이 벡터를 rhs 에 사영한 결과
	vector2 project(const vector2& rhs) const {
		vector2 r = rhs.normalize();
		return r * r.dot(*this);
	}
};

double ccw(vector2 a, vector2 b)
{
	return a.cross(b);
}
double ccw(vector2 p, vector2 a, vector2 b)
{
	return ccw(a-p, b-p);
}


typedef vector<vector2> polygon;
polygon giftWrap(const vector<vector2>& points)
{
	int n = points.size();
	polygon hull;
	vector2 pivot = *min_element(points.begin(), points.end());
	hull.push_back(pivot);
	while(true)
	{
		vector2 ph = hull.back(), next = points[0];
		for(int i=1;i<n;i++)
		{
			double cross = ccw(ph, next, points[i]);
			double dist = (next - ph).norm() - (points[i] - ph).norm();
			if(cross > 0 || (cross == 0 && dist < 0))
				next = points[i];
		}
		if(next==pivot)
			break;
		hull.push_back(next);
	}
	return hull;
}

int main() 
{
	vector<vector2> vec;
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		vec.push_back(vector2(x,y));
	}
	vector<vector2> ret = giftWrap(vec);
	cout<<ret.size()<<"\n";
	return 0;
}

https://www.acmicpc.net/problem/9240

간단하다. 볼록 껍질을 구한후 볼록 껍질의 모든 점에 대해 각각의 거리값을 특정 변수에 저장해둔다.

그다음에 가장 큰 값을 출력하면 끝.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

const double PI = 2.0 * acos(0.0);

struct vector2 {
	double x, y;
	vector2(double x_ = 0, double y_ = 0) : x(x_), y(y_) {}

	// 두 벡터가 같은 경우
	bool operator == (const vector2& rhs) const { return x == rhs.x && y == rhs.y; }

	// 벡터의 덧셈과 뺄셈, 단항 연산자의 구현
	vector2 operator + (const vector2& rhs) const { return vector2(x + rhs.x, y + rhs.y); }
	vector2 operator - (const vector2& rhs) const { return vector2(x - rhs.x, y - rhs.y); }
	vector2 operator - () const { return vector2(-x, -y); }
	bool operator < (const vector2& rhs) const 
    {
        return x != rhs.x? x < rhs.x: y < rhs.y;
    }
	// 스칼라로 곱셈
	vector2 operator * (double rhs) const { return vector2(x * rhs, y * rhs); }

	// 벡터의 길이를 반환한다
	double norm() const { return hypot(x, y); }

	// 방향이 같은 단위 벡터 (unit vector) 를 반환한다
	vector2 normalize() const { double n = norm(); return vector2(x / n, y / n); }

	// 내적/외적의 구현
	double dot(const vector2& rhs) const { return x * rhs.x + y * rhs.y; }
	double cross(const vector2& rhs) const { return x * rhs.y - rhs.x * y; }

	// 이 벡터를 rhs 에 사영한 결과
	vector2 project(const vector2& rhs) const {
		vector2 r = rhs.normalize();
		return r * r.dot(*this);
	}
};

double ccw(vector2 a, vector2 b)
{
	return a.cross(b);
}
double ccw(vector2 p, vector2 a, vector2 b)
{
	return ccw(a-p, b-p);
}


typedef vector<vector2> polygon;
polygon giftWrap(const vector<vector2>& points)
{
	int n = points.size();
	polygon hull;
	vector2 pivot = *min_element(points.begin(), points.end());
	hull.push_back(pivot);
	while(true)
	{
		vector2 ph = hull.back(), next = points[0];
		for(int i=1;i<n;i++)
		{
			double cross = ccw(ph, next, points[i]);
			double dist = (next - ph).norm() - (points[i] - ph).norm();
			if(cross > 0 || (cross == 0 && dist < 0))
				next = points[i];
		}
		if(next==pivot)
			break;
		hull.push_back(next);
	}
	return hull;
}

int main() 
{
	vector<vector2> vec;
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		vec.push_back(vector2(x,y));
	}
	vector<vector2> ret = giftWrap(vec); //볼록 껍질 좌표 목록들.
	vector<double> dis;
	for(int i=0;i<ret.size();i++)
	{
		//cout<<ret[i].x<<" "<<ret[i].y<<"\n";
		for(int j=0;j<ret.size();j++)
			if(i!=j) //두 점이 다르면 거리값을 dis벡터에 저장해둠.
				dis.push_back(sqrt(pow(ret[i].y-ret[j].y, 2) + pow(ret[i].x-ret[j].x,2)));
	}
	if(ret.size()==1) //볼록 껍질 사이즈가 1일경우 모든 점이 같다는 소리이므로 거리 0을 저장해둠.
		dis.push_back(0.0);
	cout<<setprecision(12)<<*max_element(dis.begin(), dis.end())<<"\n"; //10^-6의 정확도 + max_element로 결과값을 구해줌.
	//for(int i=0;i<dis.size();i++)
	//	cout<<setprecision(11)<<dis[i]<<endl;
	return 0;
}