pushback

 문제에 뭔가 열심히 적혀있는데 결국엔 두 원이 만나는 점의 개수를 구하면 된다.

 두 원의 중심이 같으면 반지름에 따라 모든 점에서 만나거나 만나는 점이 없다.

 중심이 다르면 만나지 않거나, 한 점에서 접하거나, 두 점에서 만나게 된다.

 이 개념만 알고 코딩하면 되는데 그게 마음처럼 쉽게 안된다. 그래서 아마 이 글을 보고 있을 것이다.

 하나씩 짚어보자.

 두 원의 중심이 같으면 반지름이 같은지 확인하여 반지름이 같으면 -1 출력, 다르면 0을 출력해주면 된다.

 문제는 중심이 다를 때이다. 

 중심이 다를 때 만나지 않는 경우는 두 가지이다.

 두 원이 아주 떨어져 있거나, 한 원 안에 다른 원이 들어가 있는 경우인데 나같은 경우 아주 떨어진 경우만 생각했다가 두번의 WA를 받았다. 

 이 두 상황을 판단하는 방법은

• 두 원이 아주 떨어져 있는 경우 : 두 원의 반지름의 합 < 두 중심 사이의 거리
• 한 원 안에 다른 원이 있는 경우 : 두 원의 반지름의 차 > 두 중심 사이의 거리  

 이다.

마찬가지로 두 원이 한 점에서 만나는 경우는

그림과 같이 두 가지 경우가 나온다. 

• 두 원이 떨어져 있는 경우 : 두 원의 반지름의 합 == 두 중심 사이의 거리
• 한 원 안에 다른 원이 있는 경우 : 두 원의 반지름의 차 == 두 중심 사이의 거리  

마지막으로 두 원이 두 점에서 만나는 경우는

 위와 같이 두 가지 경우인 것 같아 보여서 아래와 같이 

• 두 원이 떨어져 있는 경우 : 두 원의 반지름의 합 > 두 중심 사이의 거리
• 한 원 안에 다른 원이 있는 경우 : 두 원의 반지름의 차 < 두 중심 사이의 거리 

 나누어 생각하면 망한다. 사실 위에 두 경우는 같은 경우이므로, 두 점에서 만날 때는 위에 두 조건을 동시에 만족해야한다.  

 결론적으로 중심이 다를 때 두 원의 중심 사이의 거리를 $d$, 두 원의 반지름을 $r_1$, $r_2$라고 하면,

• 교점 X : $r_1+r_2<d$    or    $|r_1-r_2|>d$
• 교점 1 : $r_1+r_2=d$    or    $r_1-r_2=d$
• 교점 2 : $|r_1-r_2|<d<r_1+r_2$

 이렇게 정리할 수 있고, 코딩만 하면 끝난다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    int first_x, first_y, first_r, second_x, second_y, second_r;
    int d, r;
    
    while (T--) {
        cin >> first_x >> first_y >> first_r >> second_x >> second_y >> second_r;
        // d : (두 점 사이의 거리) ^ 2
        d = (first_x - second_x) * (first_x - second_x) + (first_y - second_y) * (first_y - second_y);

        // 중심이 같은 경우
        if (d == 0) {
            if (first_r == second_r) {
                cout << -1 << '\n';
            }
            else{
                cout << 0 << '\n';
            }
        }
        // 중심이 다를 때
        else {
            // 미리 구해놓은 d가 거리의 제곱이므로 양변을 제곱해준다.
            // r1 + r2 < d || |r1 - r2| > d
            if ((first_r + second_r) * (first_r + second_r) < d || d < (first_r - second_r) * (first_r - second_r) ) {
                cout << 0 << '\n';
            }
            // r1 + r2 == d || |r1 - r2| == d
            else if ((first_r + second_r) * (first_r + second_r) == d || (first_r - second_r) * (first_r - second_r) == d) {
                cout << 1 << '\n';
            }
            // |r1 - r2| < d < r1 + r2
            else if ((first_r - second_r) * (first_r - second_r) < d && d < (first_r + second_r) * (first_r + second_r) ){
                cout << 2 << '\n';
            }
        }
    }

    return 0;
}

 유클리드 기하학에서 원의 넓이는 우리가 아는 원의 넓이이고,

 택시 기하학에서 원의 넓이는 대각선의 길이가 $2n$인 정사각형의 넓이와 같다.

 실수 출력에서만 조금 신경 써주면 충분히 해결할 수 있는 문제이다.

 아래 코드에 printf를 이용한 실수 출력과 cout을 이용한 실수 출력 두 가지 모두 적어놓았으니, 이 부분은 외우자.

#include <bits/stdc++.h>

#define pi 3.14159265359
using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX_N = 1e5 + 1;
const int MOD = 1e+9;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	
    double n;
    cin >> n;

    // printf
    // 소수점 아래 x자리만큼 출력하고 싶으면 %0.xf로 사용
    printf("%0.7f\n%0.7f", n * n * pi, n * n * 2);
    
    // cout
    cout << fixed; // 소수점 자리수를 고정함
    cout.precision(7); // 몇 자리를 출력할지 정함
    cout << n * n * pi << '\n' << n * n * 2; // fixed

    return 0;
}

 간단하게 우리가 알고 있는 피타고라스를 쓰면 된다. 대신 컴퓨터는 항상 정확한 루트 값을 갖고 온다는 가정을 할 수 없기 때문에, 

$가장긴변=\sqrt{한{변}^2+다른한{변}^2}$ 이 아닌

$가장긴{변}^2=한{변}^2+다른한{변}^2$ 을 만족하는지 확인한다.

 당연하게도 가장 긴 변은 빗변이겠지만, 문제에서 빗변이 어떤 것인지 입력으로 알려주지 않기 때문에 입력을 받아 가장 긴 변을 빗변으로 설정해주어야 한다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    vector<int> v(3);
    while (true) {
        cin >> v[0] >> v[1] >> v[2];
        if (v[0] == 0 && v[1] == 0 && v[2] == 0)
            break;
        sort(v.begin(), v.end());

        if (v[2] * v[2] == v[0] * v[0] + v[1] * v[1]){
            cout << "right\n";
        }
        else{
            cout << "wrong\n";
        }
    }
    return 0;
}

 세 점을 갖고 상대적으로 위치를 찾아내는 방법도 있겠지만, 생각보다 귀찮(?)아서 1001개짜리 배열 $x$와 $y$을 이용해서 풀었다.

 풀이는 이렇다.

 1. 입력 받은 세 점의 좌표에 해당하는 원소들을 먼저 1씩 증가시켜준다.

 2. $x$와 $y$배열을 1~1000까지 돌면서 원소가 1인 곳을 체크해서 답으로 저장해준다.

 3. 찾은 좌표를 출력한다.

 직사각형이기 때문에 네 점의 좌표는 항상 (a, c) , (a, d), (b, c), (b, d)의 형태를 유지한다는 점을 이용하였다. ( 항상 a, b, c, d가 2개씩 등장)

#include <bits/stdc++.h>
using namespace std;

int x[1001] = { 0 , };
int y[1001] = { 0 , };

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    
	for (int i = 0; i < 3; i++) {
		int a, b;
		cin >> a >> b;
		x[a]++;
		y[b]++;
	}
	
	int ans_x = -1, ans_y = -1;
    
	for (int i = 0; i < 1001; i++) {
		if (x[i] == 1) ans_x = i;
		if (y[i] == 1) ans_y = i;
		if (ans_x != -1 && ans_y != -1)
			break;
	}
	
	cout << ans_x << ' ' << ans_y;

	return 0;
}

$(x,y)$가 직사각형 안에 존재하는 점이기 때문에 직사각형의 네 경계선까지 거리는 무리없이 구할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int x, y, w, h;
	cin >> x >> y >> w >> h;
	int ans = min({x, w - x, y, h - y});
	cout << ans;
	return 0;
}

정답 코드를 바로 보기보다는 아래 글을 먼저 읽고 푸시길 바랍니다.

https://pushback.tistory.com/8

 입력으로 들어오는 $n$의 범위가 $1\le n\le 10,000$이라 에라토스테네스의 체가 필요없을 수도 있다고 생각할 수 있다.

 하지만 테스트 케이스의 수가 존재하고 문제에서 언급은 안되어 있지만 대략 $T$의 범위가 $1\le T\le 10,000$라고 가정했을 때, 우리는 최악의 상황에서 $(10,000\ast 10,000)$번의 나누기 연산이 필요하다.

 TLE의 위험이 도사리고 있으니 안전하게 에라토스테네스의 체를 사용하자.  그냥 소수 문제에선 에라토스테네스의 체가 거의 정답이다.

 에라토스테네스의 체를 사용하여 $110,000$ 사이에 있는 모든 소수를 구했다고 가정하자.

 어떤 입력 $n$이 들어왔을 때, 우리는 $x+y=n,(x\le y)$을 만족하는 두 소수 $x,y$가 있다고 가정하면 $x$는 $2\le x\le \frac{n}{2}$을 만족한다.

 결국, $2$부터 $\frac{n}{2}$까지 for문을 돌면서 $x$와 $n-x$가 둘 다 소수인 경우를 구해주면 된다.

 $2$부터 for문을 돌 때 두 수의 차가 가장 적은 것을 찾아야하므로, 찾을 때마다 답을 update해주면 마지막으로 나온 답은 자동적으로 두 수의 차가 가장 적은 경우가 된다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX_N = 1e4 + 1;
const int MOD = 1e+9;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

bool isPrime[MAX_N];

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    memset(isPrime, 1, sizeof(isPrime));

    isPrime[1] = false;
    for (int i = 2; i < MAX_N; ++i) {
        if (isPrime[i]) {
            for (ll j = i * 1LL * i; j < (ll) MAX_N; j += i * 1LL) {
                isPrime[j] = false;
            }
        }
    }

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int left = 2, right;

        for (int x = 2; x <= (n / 2); x++) {
            if (isPrime[x] && isPrime[n - x]) {
                left = x;
                right = n - x;
            }
        }
        cout << left << ' ' << right << '\n';
    }

    return 0;
}

정답 코드를 바로 보기보다는 아래 글을 먼저 읽고 푸시길 바랍니다.

https://pushback.tistory.com/8

 $n$의 범위가 $1\le n\le 123,456$이므로, 에라토스테네스의 체로 해결하는게 가장 빠른 시간안에 해결할 수 있을 것으로 보인다. 에라토스테네스의 체를 사용해보자.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX_N = 123457 * 2;
const int MOD = 1e+9;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

bool isPrime[MAX_N];

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    memset(isPrime, 1, sizeof(isPrime));

    isPrime[1] = false;
    for (int i = 2; i < MAX_N; ++i) {
        if (isPrime[i]) {
            for (ll j = i * 1LL * i; j < (ll) MAX_N; j += i * 1LL) {
                isPrime[j] = false;
            }
        }
    }

    while (true) {
        int n, cnt = 0;
        cin >> n;
        if (n == 0) break;
		
        for (int i = n + 1; i <= 2 * n; i++) {
            if (isPrime[i]) {
                cnt++;
            }
        }
        cout << cnt << '\n';
    }

    return 0;
}

정답 코드를 바로 보기보다는 아래 글을 먼저 읽고 푸시길 바랍니다.

https://pushback.tistory.com/8

 입력의 범위가 $1\le M\le N\le 1,000,000$ 이므로 숫자 하나하나를 naive한 방법이나 naive하게 $\text{Could not find of for root}$까지 보는 방법으로 소수를 판별해서 시간 안에 통과하기는 쉽지 않아 보인다. 따라서 에라토스테네스의 체를 쓰자.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX_N = 10e+6 + 1;
const int MOD = 1e+9;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

bool isPrime[MAX_N];

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    memset(isPrime, 1, sizeof(isPrime));

    int M, N;
    cin >> M >> N;

    isPrime[1] = false;
    for (int i = 2; i <= N; ++i) {
        if (isPrime[i]) {
            for (ll j = i * 1LL * i; j <= (ll) N; j += i * 1LL) {
                isPrime[j] = false;
            }
        }
    }

    for (int cur = M; cur <= N; ++cur) {
        if (isPrime[cur]) {
            cout << cur << '\n';
        }
    }

    return 0;
}

한가지 재미있는 점은 isPrime 배열을 매번 1,000,000개에 대해 초기화 해주면 아래와 같이 64ms이 걸리고,

위 코드와 같이 N의 범위에 맞춰서 초기화 해주면 16ms가 걸린다.