algolab은 국민대학교 소프트웨어학부 수업에서 사용되는 온라인 저지?(과제 제출 사이트)입니다.
1주차, 2주차 과제와 마찬가지로, 3주차 과제 제출 기한이 끝났기 때문에, 한번 풀이를 작성해보겠습니다.
10. 수직수평성분의교차
첫번째 문제인데, 이 문제가 가장 설명하기 어려운 것 같습니다...
바로 코드부터 보고, 코드로 설명을 해보겠습니다.
#include <iostream>
using namespace std;
int tc,a[4],b[4];
int f[3]; // y좌표, x0, x1
int e[3]; // x좌표 y0 y1
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> tc;
while(tc--) {
for(int x=0; x<4; x++) cin >> a[x];
for(int x=0; x<4; x++) cin >> b[x];
if(a[0] == a[2]) {
e[0] = a[0];e[1] = a[1];e[2] = a[3];
if(e[1] > e[2]) {
int tmp = e[1];e[1] = e[2]; e[2] = tmp;
}
f[0] = b[1];f[1] = b[0];f[2] = b[2];
if(f[1] > f[2]) {
int tmp = f[1];f[1] = f[2];f[2] = tmp;
}
}
else {
e[0] = b[0];e[1] = b[1];e[2] = b[3];
if(e[1] > e[2]) {
int tmp = e[1];e[1] = e[2];e[2] = tmp;
}
f[0] = a[1];f[1] = a[0];f[2] = a[2];
if(f[1] > f[2]) {
int tmp = f[1];f[1] = f[2];f[2] = tmp;
}
}
if((e[1] < f[0] && f[0] < e[2]) && f[1] < e[0] && e[0] < f[2]) {
cout << "1\n";
}
else {
if(((e[1] <= f[0] && f[0] <= e[2]) && f[1] <= e[0] && e[0] <= f[2]) ) {
cout<<"2\n";
}
else {
cout<<"0\n";
}
}
}
}f 배열: y좌표가 같은 점을 이은 선분의 좌표들을 표시합니다. (해당 y좌표, 시작점의 x좌표, 끝점의 y좌표), (시작점 < 끝점)
e 배열: x좌표가 같은 점을 이은 선분의 좌표들을 표시합니다. (해당 x좌표, 시작점의 y좌표, 끝점의 y좌표), (시작점 < 끝점)
아무튼, 코드가 굉장히 복잡한 부분은 이 f배열과 e배열을 가공하는 것이니 넘기시고 이 부분이 중요합니다.
if((e[1] < f[0] && f[0] < e[2]) && (f[1] < e[0] && e[0] < f[2])) {
cout << "1\n";
}
else {
if(((e[1] <= f[0] && f[0] <= e[2]) && (f[1] <= e[0] && e[0] <= f[2]))) {
cout<<"2\n";
}
else {
cout<<"0\n";
}
}생각보다 if 안에 조건이 간단합니다.
일단, 두 선분이 교차한다는 것은 이 조건을 만족해야 합니다.
f배열 시작점 x좌표 < e배열의 해당 x좌표 < f배열 끝점 x좌표
e배열 시작점 y좌표 < f배열 해당 y좌표 < e배열 끝점 y좌표
그리고, 이경우를 제외하고 나서, 두선분이 접한다는 것은 이 조건을 만족하면됩니다.
f배열 시작점 x좌표 <= e배열의 해당 x좌표 <= f배열 끝점 x좌표
e배열 시작점 y좌표 <= f배열 해당 y좌표 <= e배열 끝점 y좌표
위의 경우를 모두 제외하면, 서로 교차하지 않는것입니다.
사실 더 간단한 알고리즘들이 있긴 하지만 생각나지 않아서, 이정도로 구현해서 제출했습니다.
위의 조건들이 왜 성립하게 되는가는 한번 그림을 그려보시거나 테스트케이스를 대입해보시면 이해하실 것 같습니다.
11. 삼각형의종류-2
이 문제는 double을 최대한 사용하지 않는 게 key point였습니다.
일단, 간단하게 생각을 해봅시다.
현재 이 문제는 다음 12번 문제처럼 어떤 길이를 주는 것이 아니라, 점들의 좌표를 주었습니다.
그러면, 어떻게 되든간에 세 개의 점이 직선을 이루지 않으면 삼각형을 형성합니다.
이제 알아야 하는 것은 직선을 어떻게 판단하느냐 입니다.
제가 주로 하는 방식은 이것입니다.
위 그림에서는 점들 사이의 거리를 구해놓았고, c가 가장 긴 변의 길이라고 가정한 상황입니다.
여기서 그러면, 만약 c가 a+b와 같다라는 것은 직선인 경우밖에 없다라는 것을 알 수 있습니다.
그리고 sqrt()를 써야 하는 경우도 2*a*b에서 밖에 없어서 오차가 거의 없을 것입니다.
이제 바로 코드를 보겠습니다.
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct point {
int X,Y;
};
int tc;
point p[3];
int d[3];
int dis2(point A, point B) {
return (A.X - B.X)*(A.X - B.X) + (A.Y - B.Y)*(A.Y - B.Y);
}
int main() {
cin >> tc;
while(tc--) {
int cnt =0;
for(int i=0; i<3; i++) {
cin >> p[i].X >> p[i].Y;
}
for(int i=0; i<3; i++) {
for(int j=i+1; j<3; j++) {
d[cnt++] = dis2(p[i],p[j]);
}
}
sort(d,d+3);
if(d[2] >= d[0] + d[1] + 2*sqrt(d[0]*d[1])) {
cout << "0\n";
}
else {
if (d[2] == d[0] + d[1]) {
cout<< "1\n";
}
else if(d[2] > d[0] + d[1]) {
cout<<"2\n";
}
else cout<<"3\n";
}
}
}
12. 삼각형의종류-1
이 문제가 이번주차에서 쉬운 문제에 속하는 문제였던 것 같습니다.
일단, 문제에 주어지는 a,b,c를 그대로 가져와 설명해보겠습니다.
삼각형이 만들어지지 않는 경우는, 가장 긴 변의 길이인 c가 (a+b) 보다 크거나 같은 경우입니다.
이 경우가 가장 먼저 걸러지고, 그다음으로 문제에서 주어진 순서대로 정삼각형, 직각삼각형, 이등변삼각형, 일반 삼각형을 판단하면 되겠습니다.
#include <iostream>
using namespace std;
int tc,a,b,c;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> tc;
while(tc--) {
cin >> a >> b >> c;
// 삼각형이 성립안하는 경우
if(c >= (a+b)) {
cout << "0\n";
}
else {
// 정삼각형
if(a == b && b == c) {
cout<<"1\n";
}
// 직각삼각형
else if(c*c == a*a + b*b) {
cout<<"2\n";
}
// 이등변삼각형
else if(a==b || b==c) {
cout<<"3\n";
}
// 일반 삼각형
else {
cout<<"4\n";
}
}
}
}
13. 삼각형면적
이 문제는 문제에서 주어지는 조건을 그대로 활용하면 풀 수 있었던 문제입니다.
(괜히 2로 나누는 순간 틀릴 위험이 있습니다..)
별다른 설명은 필요가 없을 것 같고, 바로 코드를 올리겠습니다.
#include <iostream>
using namespace std;
int tc,ax,ay,bx,by,cx,cy;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> tc;
while(tc--) {
cin >> ax >> ay >> bx >> by >> cx >> cy;
int S = ((bx - ax)*(cy-ay)) - ((cx-ax)*(by-ay));
if(S > 0) {
cout << S << " 1\n";
}
else if(S < 0) {
cout << -S << " -1\n";
}
else {
cout << "0 0\n";
}
}
}14. 사각형과점과의거리
이 문제는 좀 case를 나누는 것이 필요합니다.
+ 추가) 다른 분들이 제출한 코드를 보니까 굳이이이이이이 케이스를 나누지 않고 직사각형 내의 모든 좌표와 거리를 비교하는 코드도 시간 내로 통과가 되네요 :) 이게 더 간단한 풀이인 것 같습니다. 비록 시간 복잡도가 최적은 아니더라도, 되면 된 거니까요 ㅎㅎ
아래 그림과 같이 경우를 나눕시다!
위 그림처럼, 직사각형의 좌표를 기준으로 점이 오는 경우를 9개로 나눕니다.
1번 경우) 그냥 거리를 0 0 으로 하면 됩니다.
2번 경우) 이때는, x좌표를 고려할 이유가 없습니다. 주어지는 직사각형의 y좌표 2개 중에 가까운 y좌표와의 차이만 구하면 됩니다.
3번 경우) 2번 경우와 비슷합니다. 이때는 y좌표를 고려할 이유가 없습니다.
4번 경우) 여기서 조금 복잡하게 하자면, 4번 내에서도 모든 범위를 나누고 거리를 구하면 되지만, 저는 그냥 직사각형 4개의 꼭짓점 4개를 다 구해놓고, 이 4개의 점들 사이의 거리 중 최소값을 구해냈습니다.
코드는.. 조금, 더럽게 짠것 같습니다...
왜냐하면, 알고랩의 버전상
아래 같은 코드를 지원하지 않아, vector에 일일이 data를 넣어줬기 때문입니다.
struct point {
int X,Y;
};
vector <point> V = {{x1,y1},{x1,y2},{x2,y1},{x2,y2}};
이걸 몰라서.. 틀릿회수 증가
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct point {
int X,Y;
};
int tc;
int x1,y1,x2,y2;
int x,y;
int dis2(point A, point B) {
return (A.X - B.X)*(A.X - B.X) + (A.Y - B.Y)*(A.Y - B.Y);
}
int disTaxi(point A, point B) {
return abs(A.X - B.X) + abs(A.Y - B.Y);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> tc;
while(tc--) {
cin >> x1 >> y1 >> x2 >> y2;
cin >> x >> y;
// 포함.
if(x1 <= x && x <= x2 && y1 <= y && y <= y2) {
cout << "0 0\n";
}
// 십자가 영역
else if((x1 <= x && x <= x2) || (y1 <= y && y <= y2)) {
if(x1 <= x && x <= x2) {
int d = min(abs(y-y1),abs(y-y2));
cout << d*d << " " << d << "\n";
}
else {
int d = min(abs(x-x1),abs(x-x2));
cout << d*d << " " << d << "\n";
}
}
// 그 외의 영역
else {
int mn0 = 123456789;
int mn1 = 123456789;
vector <point> V;
point Z;
Z.X = x1;Z.Y = y1;
V.push_back(Z);
Z.X = x2;Z.Y = y1;
V.push_back(Z);
Z.X = x1;Z.Y = y2;
V.push_back(Z);
Z.X = x2;Z.Y = y2;
V.push_back(Z);
point current;
current.X = x;
current.Y = y;
for(int i=0; i < 4; i++) {
mn0 = min(mn0,dis2(V[i],current));
mn1 = min(mn1,disTaxi(V[i],current));
}
cout << mn0 <<" "<<mn1 << "\n";
}
}
}
이번엔 비교적 수학 문제가 많이 나온 것 같습니다.
힘드네요..
Rmx
'KMU > algolab' 카테고리의 다른 글
| [KMU - algolab] c++ 프로그래밍 week 5 과제 풀이 (0) | 2020.04.27 |
|---|---|
| [KMU - algolab] c++ 프로그래밍 week 4 과제 풀이 (0) | 2020.04.20 |
| [KMU - algolab] c++ 프로그래밍 파일 입출력 (5) | 2020.04.14 |
| [KMU - algolab] c++ 프로그래밍 week 2 과제 풀이 (2) | 2020.04.06 |
| [KMU - algolab] c++ 프로그래밍 week 1 과제 풀이 (1) | 2020.03.31 |