청정알고리즘

문제

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

풀이

전형적인 Convex Hull 문제이다.

아래 풀이에서는 Graham Scan이라고 하는 $O(nlogn)$의 알고리즘을 사용한다.

Convex Hull을 구한 후, Convex Hull 상에서 가장 먼 두 점을 찾는데, 원래는 Rotating Calipers 라는 알고리즘을 사용하여 $O(n)$에 구해야 한다.

하지만 필자는 한 번도 구현해본 적이 없고, 실제 이 문제에서는 좌표의 범위가 작고, 정수점만 입력으로 들어오기때문에 Convex Hull의 점의 수가 매우 작고, 실제로 1000*4=4000개보다 작음은 약간의 논증을 통해 보일 수 있다.

따라서 Convex Hull 내부의 모든 점을 비교해도 시간안에 구할 수 있다.

정해는 rotating calipers라는 알고리즘을 이용해서 가장 먼 두 점을 구하는데 $O(|convex hull|)$이면 충분하다.

Time Complexity : $O(nlogn + |convex hull|^2)$

코드

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define N 100002
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pos;
 
double dist(pos p1, pos p2)
{
	double dissq = (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second);
	return sqrt(dissq);
}

int n;

vector<pos> p;

ll ccw(pos p1, pos p2, pos p3)
{
	return (p2.first - p1.first)*(p3.second - p1.second) - (p2.second - p1.second)*(p3.first - p1.first);
}

bool cmp(pos p1, pos p2)
{
	ll c = ccw(p[0], p1, p2);
	if (c > 0) return 1;
	if (c < 0) return 0;
	else
    {
		if (dist(p[0], p1) < dist(p[0], p2)) return 1;
		else return 0;
	}
}

int main()
{
	cin>>n;

	p.resize(n);
	for (int i=0;i<n;i++) cin>>p[i].first>>p[i].second;
	
	sort(p.begin(),p.end());
	sort(p.begin()+1,p.end(),cmp);
    
	vector<pos> cvxh;
	cvxh.push_back(p[0]);
	cvxh.push_back(p[1]);

	for (int i=2;i<n;i++)
	{
		while (cvxh.size() >= 2 && ccw(cvxh[cvxh.size()-2],cvxh.back(),p[i])<=0)
			cvxh.pop_back();
		cvxh.push_back(p[i]);
	}
    
	double ans=-1;
	int len=cvxh.size();
	for (int i=0;i<len;i++) for (int j=i+1;j<len;j++)
		ans=max(ans, dist(cvxh[i], cvxh[j]));

    printf("%.10f", ans);
}

문제

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

풀이

$x,y$가 input으로 들어올때, $f(x)=$(1부터 $x$까지 적었을 때, 나타나는 0~9의 숫자의 배열)이라고 정의하자.

그럼 구하고자 하는 정답은 $f(y)-f(x-1)$이 된다.

그럼 $f(x)$는 어떻게 구할까?

자릿수별로 각 숫자의 개수를 계산한다는 아이디어를 기본적으로 생각해보자.

즉, 1의 개수를 셀때, 1의 자리에 오는 1, 10의 자리에 오는 1, 100의 자리에 오는 1,....들을 모두 세서 더해준다면 구하고자하는 전체 1의 개수를 구할 수 있을 것이다.

결국 위의 질문은 1~x까지의 숫자중 $10^t$자리가 $a$인 숫자가 모두 몇개인지를 각 $t$에 대해 모두 풀어서 더해주면 된다.

이는 다음과 같이 경우를 나누어 풀수 있다.

case 1) $a$가 $x$의 $10^t$자리 숫자보다 작을 경우

예를 들어서 $x=12345, a=1, 10^t=100$인 경우를 보자.

그러면 ??1?? 꼴의 숫자가 몇 개인지를 세는 것인데, 이는 (찾는 자리수보다 높은 자리에 올수 있는 숫자들의 종류) * 100이 된다.

또한 (찾는 자리수보다 높은 자리에 올수 있는 숫자들의 종류)는 위의 예시에서는 0부터 12까지이므로, 총 13개가 가능하다.

즉 1??, 11??, 21??, 31??, ... , 121??의 경우가 가능하다는 뜻이다.

수식으로 나타내면 $(x/10^{t+1}+1)\times 10^t$가지 경우임을 알 수 있다.

case 2) $a$가 $x$의 $10^t$자리 숫자와 같을 경우

$x=12345, a=3, 10^t=100$을 예로 들어보자.

이 경우에는 3??, 13??, ..., 113??까지는 자유롭게 가능하고, 123??의 경우에는 0~45까지 총 46개만 가능하다.

같은 방식으로 수식으로 나타내면 $(x/10^{t+1})\times 10^t+(x%10^t)+1$ 가지 경우가 있음을 알 수 있다.

case 3) $a$가 $x$의 $10^t$자리 숫자보다 클 경우

비슷한 방식으로  $x=12345, a=5, 10^t=100$을 예로 들어보자.

이 경우에는 5??, 15??, ..., 115??까지만 가능하므로 case 1)의 경우보자 $10^t$개 적게 된다.

따라서 이 경우는 $(x/10^{t+1})\times 10^t$ 가지이다.

따라서 이를 모두 각각 더해주면 된다.

주의할 점은 맨 앞자리에 0이 올수는 없으므로 0은 각 경우에서 $10^t$개만큼 빼주어야 한다는 점이다.

즉 10?? 꼴의 숫자는 있지만, 0?? 꼴의 숫자는 존재하지 않으므로, 이 경우를 빼주는 것이다.

위와 같은 방식으로 0~9까지 등장수를 모두 더해주면 $f(x)$를 구할 수 있다.

Time Complexity : $O(logx+logy)$

코드

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

vector<int> f(int t)
{
	vector<int> ret(10);
	for(int i=1;i<=t;i*=10)
	{
		for(int j=0;j<10;j++)
		{
			if( j<(t/i)%10) ret[j] += (t/(i*10)+1)*i;
			else if( j==(t/i)%10 ) ret[j] += (t/(i*10))*i+(t%i)+1;
			else ret[j] += (t/(i*10))*i;
		}
		ret[0]-=i;
	}
	return ret;
}
int main() {
	while(1)
	{
		int x,y;
		cin>>x>>y;
		if(x==0 && y==0)break;
		vector<int> a1 = f(y);
		vector<int> a2 = f(x-1);
		for(int i=0;i<10;i++)
		{
			cout<<a1[i]-a2[i]<<" ";
		}
		cout<<"\n";
	}
}

문제

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

풀이

단순히 생각하면 30000 * 30000 배열을 만들어 사각형이 입력으로 들어오면 해당 사각형의 영역에 1씩 더해준다.

그 후, 1이상의 값을 가지는 모든 칸의 값을 세주면 된다.

하지만 이와 같은 방법으로는 시간도 많이 소모하고, 공간도 많이 잡는다.

따라서 line sweeping 알고리즘을 사용하여 현재 line과 닿아있는 부분의 30000개 배열만 생각한다.

세로 선을 왼쪽 끝부터 오른쪽 끝까지 sweeping한다고 생각하자.

sweeping하면서 만나는 면적을 모두 더하면 구하고자 하는 정답이 된다.

sweeping 하면서 발생하는 event의 종류가 두 가지인데, 각각에 대해서 처리해 주면 된다.

case 1) 새로운 사각형의 등장

이 때는 현재 직사각형의 왼쪽변에 처음 닿게 된다.

이 때, 이 변에 해당하는 y좌표를 가진 부분에 1씩 증가시켜준다.

case 2) 사각형의 퇴장

이 때는 현재 직사각형의 오른쪽변에 처음 닿게 된다.

이 때, 이 변에 해당하는 y좌표를 가진 부분에 1씩 감소시켜준다.

위와 같은 과정을 거치면서 현재 line에 있던 1이상의 칸의 수를 모두 더해주면 된다.

하지만 이렇게 되면 $O(nC)$의 시간복잡도로 시간안에 통과할 수 없다.

따라서 전체 구간의 합을 segment tree를 이용하여 관리해주면 된다.

이 때, 등장하는 쿼리는 구간에 1을 더해주는 query이므로, lazy propagation의 아이디어를 사용한다.

lazy propagation처럼 게으르게 값을 관리하는데, 현재 구간이 전파될 예정이라면, 하위 노드의 값과 관계 없이 이 구간은 모두 값을 구하는데 사용되게 된다.

root 노드로 부터 내려가다가 처음으로 전파될 예정인 노드를 만나면 바로 그 하위 구간의 길이를 return해주면 되기 때문에, 전파과정은 진행하지 않아도 무방하다.

이러한 방법을 이용하여 segment tree를 업데이트 해주면, event마다 log 시간복잡도에 원하는 작업을 완료할 수 있다.

Time Complexity : $O(N(logN+logC))$

코드

#include<iostream>
#include<algorithm>
#define N 10005
#define C 40000
#define lc(i) ((i)<<1)
#define rc(i) ((i)<<1|1)

using namespace std;

struct ev
{
	int x, y1, y2, z;
	bool operator<(const ev & t)
	{
		return x<t.x;
	}
}evt[N<<1];

ev make_ev(int X, int Y1, int Y2, int Z)
{
	ev r;
	r.x=X;
	r.y1=Y1;
	r.y2=Y2;
	r.z=Z;
	return r;
}
struct segtree
{
	int val;
	int num;
} seg[C<<2];

int n,pr,ans;

void update(int l, int r, int v, int t, int x, int y)
{
	if(y<l || r<x) return;
	if(l<=x && y<=r) seg[t].num+=v;
	else
	{
		int mid=(x+y)>>1;
		update(l,r,v,lc(t),x,mid);
		update(l,r,v,rc(t),mid+1,y);
	}
	if(seg[t].num) seg[t].val=y-x+1;
	else seg[t].val=(x==y?0:seg[lc(t)].val+seg[rc(t)].val);
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int a,b,c,d;
		cin>>a>>b>>c>>d;

		evt[i]=make_ev(a,b,d-1,1);
		evt[i+n]=make_ev(c,b,d-1,-1);
	}
	sort(evt,evt+2*n);
	for(int i=0;i<2*n;i++)
	{
		if(i>0) ans+=(evt[i].x-pr)*seg[1].val;
		update(evt[i].y1, evt[i].y2, evt[i].z,1,0,C);
		pr=evt[i].x;
	}
	cout<<ans;
}