acmicpc.net 3878(볼록 껍질, 기하), 2254(볼록 껍질, 기하), 2166(기하)

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

1. n의 점 집합에 대해 볼록 껍질을 만든다.

2. m의 점 집합에 대해 볼록 껍질을 만든다.

3. 두 볼록 껍질이 교차하는지 검사한다. 교차하면 NO. 교차안하면 YES다.

종만북에서 소스를 가져왔다.

#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cassert>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

const double EPSILON = 1e-8;
const double PI = 2.0 * acos(0.0);

// 2차원 벡터를 표현한다
struct vector2 {
	double x, y;
	explicit vector2(double x_ = 0, double y_ = 0) : x(x_), y(y_) {}

	// 두 벡터의 비교
	bool operator == (const vector2& rhs) const { return x == rhs.x && y == rhs.y; }
	bool operator < (const vector2& rhs) const { if(x != rhs.x) return x < rhs.x; return 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); }

	// 스칼라로 곱셈
	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); }

	// x축의 양의 방향으로부터 이 벡터까지 반시계방향으로 잰 각도
	double polar() const { return fmod(atan2(y, x) + 2*PI, 2*PI); }

	// 내적/외적의 구현
	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);
	}
};

// 원점에서 벡터 b 가 벡터 a 의 반시계 방향이면 양수, 시계 방향이면 음수, 평행이면 0 을 반환한다
double ccw(vector2 a, vector2 b) {
	return a.cross(b);
}

// 점 p 를 기준으로 벡터 b 가 벡터 a 의 반시계 방향이면 양수, 시계 방향이면 음수, 평행이면 0 을 반환한다
double ccw(vector2 p, vector2 a, vector2 b) {
	return ccw(a-p, b-p);
}

// 두 구간 [a,b], [c,d] 가 교집합이 없는지 여부를 확인한다
double disjoint(double a, double b, double c, double d) {
	if(a > b) swap(a, b); if(c > d) swap(c, d);
	return b < c || d < a;
}

// 두 선분이 서로 접촉하는지 여부를 반환한다
bool segmentIntersects(vector2 a, vector2 b, vector2 c, vector2 d) {
	double ab = ccw(a, b, c) * ccw(a, b, d);
	double cd = ccw(c, d, a) * ccw(c, d, b);
	// 두 선분이 한 직선 위에 있는 경우
	if(ab == 0 && cd == 0)
		return !disjoint(a.x, b.x, c.x, d.x) &&
			!disjoint(a.y, b.y, c.y, d.y);
	return ab <= 0 && cd <= 0;
}

// 점 q 가 다각형 p 안에 포함되어 있을 경우 참, 아닌 경우 거짓을 반환한다.
// q 가 다각형의 경계 위에 있는 경우의 반환값은 정의되어 있지 않다.
bool isInside(vector2 q, const vector<vector2>& p) {
	int crosses = 0;
	for(int i = 0; i < p.size(); ++i) {
		int j = (i + 1) % p.size();
		// (p[i], p[j]) 가 반직선을 세로로 가로지르는가?
		if((p[i].y > q.y) != (p[j].y > q.y)) {
			double atX = (p[j].x - p[i].x) * (q.y - p[i].y) / (p[j].y - p[i].y) + p[i].x;
			if(q.x < atX)
				++crosses;
		}
	}
	return crosses % 2 > 0;
}


typedef vector<vector2> polygon;

// points 에 있는 점들을 모두 포함하는 최소의 볼록 다각형을 찾는다
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) {
		// (p - ph) 가 가장 왼쪽인 점을 찾는다. 평행인 점이 여러 개 있으면
		// 가장 먼 것을 선택한다.
		vector2 ph = hull.back(), next = points[0];
		for(int i = 1; i < n; i++) {
			double cross = (next - ph).cross(points[i] - ph);
			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;
}



// 두 다각형이 서로 닿거나 겹치는지 여부를 반환한다.
// 한 점이라도 겹친다면 true 를 반환한다.
bool polygonIntersects(const polygon& p, const polygon& q) {
	int n = p.size(), m = q.size();
	// 우선 한 다각형이 다른 다각형에 포함되어 있는 경우를 확인하자
	if(isInside(p[0], q) || isInside(q[0], p)) return true;
	// 이외의 경우, 두 다각형이 서로 겹친다면 서로 닿는 두 변이 반드시 존재한다
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			if(segmentIntersects(p[i], p[(i+1)%n], q[j], q[(j+1)%m]))
				return true;
	return false;
}


int main(int argc, char* argv[]) 
{
	int cases;
	scanf("%d", &cases);
	while(cases--) 
	{
		vector<vector2> inputs[2];
		int n, m;
		int x, y;
		scanf("%d %d", &n, &m);
		for(int i = 0; i < n; i++) {
			scanf("%d %d", &x, &y);
			inputs[0].push_back(vector2(x, y));
		}
		for(int i = 0; i < m; i++) {
			scanf("%d %d", &x, &y);
			inputs[1].push_back(vector2(x, y));
		}
		polygon hulls[2];
		for(int i = 0; i < 2; i++) 
			hulls[i] = giftWrap(inputs[i]);
		if(polygonIntersects(hulls[0], hulls[1]))
			printf("NO\n");
		else
			printf("YES\n");
	}
}

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

누워있다가 갑자기 아이디어가 떠올라서 풀었다.

1. 전체 좌표에 대해 볼록 껍질을 만든다.(가장 큰 볼록껍질인셈임)

2. 가장 큰 볼록껍질안에 감옥좌표가 들어가면 겹수++를 해주고 볼록껍질의 점들을 다 지운다.

3. 저장된 좌표가 0이면 break로 나와주고 좌표가 0이 아닐경우 1번으로 돌아간다.

4. 겹수를 출력한다.

1. 초기 상태다. 빨간점이 감옥이고 나머지 점들로 잘 감싼다하면 아래처럼 그려질수있다.

2. 아주 바깥쪽의 볼록껍질을 제거하면 아래처럼 된다.

3. 이런식으로 볼록껍질을 하나씩 없애주면서 울타리 +1 해주면 된다.

#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;
}
  
bool isInside(vector2 q, const vector<vector2>& p)
{
	int crosses = 0;
	for(int i=0;i<p.size();i++)
	{
		int j = (i+1)%p.size();
		if((p[i].y > q.y) != (p[j].y > q.y))
		{
			double atX = (p[j].x - p[i].x) * (q.y - p[i].y) / (p[j].y - p[i].y) + p[i].x;
			if(q.x < atX)
				++crosses;
		}
	}
	return crosses % 2 > 0;
}

int main() 
{
    vector<vector2> vec;
    int n,ox,oy;
    cin>>n>>ox>>oy;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        vec.push_back(vector2(x,y));
    }
	
	int cnt = 0;
	while(1)
	{
		vector<vector2> v;
		vector<vector2> ret = giftWrap(vec); //볼록 껍질을 구한다.
		if(isInside(vector2(ox,oy),ret)) //볼록 껍질 안에 감옥이 있으면
		{
			cnt++; //겹 수를 1 증가시키고
			for(int i=0;i<ret.size();i++) //전체 기둥에서 볼록 껍질의 좌표들을 제거한다.
				vec.erase(remove(vec.begin(), vec.end(), ret[i]), vec.end());
		}
		else
			break;
		if(vec.size()==0) //없으면 break
			break;
	}
	cout<<cnt<<"\n";
    return 0;
}

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

위 소스의 함수들을 다 가져온다. area함수로 면적을 계산해준다. 메인 함수만..

int main() 
{
    vector<vector2> vec;
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        vec.push_back(vector2(x,y));
    }
    printf("%.1f\n",area(vec));
    return 0;
}