oj.uz

답안 #208222

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208222 2020-03-10T10:28:16 Z E869120 Scissors and Tape (CEOI19_scissors) C++14
0 / 100
 5 ms 508 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

// ----------------------------------------- 幾何ライブラリ（ライブラリではない） ---------------------------------------
struct Point {
	long double px, py;
};

Point operator+(const Point& a1, const Point& a2) {
	return Point{ a1.px + a2.px, a1.py + a2.py };
}

Point operator-(const Point& a1, const Point& a2) {
	return Point{ a1.px - a2.px, a1.py - a2.py };
}

Point Div(Point a1, long double d) {
	return Point{ a1.px / d, a1.py / d };
}

long double dst(Point a1, Point a2) {
	return sqrt((a1.px - a2.px) * (a1.px - a2.px) + (a1.py - a2.py) * (a1.py - a2.py));
}

long double angle(Point V1) {
	long double J1 = V1.px / sqrt(V1.px * V1.px + V1.py * V1.py);
	long double J2 = 180.0L * acos(J1) / 3.14159265358979323846264L;
	if (V1.py >= 0) return J2;
	else return 360.0L - J2;
}

long double getangle(Point V1, Point V2, Point V3) {
	Point G1 = V1 - V2; long double IA = angle(G1);
	Point G2 = V3 - V2; long double IB = angle(G2);
	return min(fabs(IA - IB), 360.0L - fabs(IA - IB));
}

Point getproper(Point V2, Point V1, Point V3) {
	long double cl = 0.0L, cr = 1.0L, cm;
	for (int i = 0; i < 104; i++) {
		cm = (cl + cr) / 2.0L;
		Point I = { V1.px * cm + V3.px * (1.0L - cm), V1.py * cm + V3.py * (1.0L - cm) };
		if (getangle(V2, I, V1) < 90.0L) { cl = cm; }
		else { cr = cm; }
	}
	return Point{ V1.px * cm + V3.px * (1.0L - cm), V1.py * cm + V3.py * (1.0L - cm) };
}

// -------------------------------------------------- 本質パート -------------------------------------------------------
int N; vector<pair<long double, long double>> X;
int M; vector<pair<long double, long double>> Y;

long double G;
long double ax[1 << 18], ay[1 << 18], bx[1 << 18], by[1 << 18];
long double cx[1 << 18], cy[1 << 18], dx[1 << 18], dy[1 << 18]; bool trans[1 << 18];
long double EPS = 1.0 / 120.0;

bool equal(long double ap, long double bp) {
	if (fabs(ap - bp) < EPS) return true;
	if (min(ap, bp) / max(ap, bp) >= (1.0 - EPS)) return true;
	return false;
}

void solve(long double H1, long double W1, long double H2, long double W2, int idx) {
	if (equal(H1, H2) == true && equal(W1, W2) == true) {
		ax[idx] = 0; ay[idx] = 0; bx[idx] = H1; by[idx] = W1;
		cx[idx] = 0; cy[idx] = 0; dx[idx] = H2; dy[idx] = W2;
		trans[idx] = false;
		G = idx;
		return;
	}
	if (equal(H1, W2) == true && equal(W1, H2) == true) {
		ax[idx] = 0; ay[idx] = 0; bx[idx] = H1; by[idx] = W1;
		cx[idx] = 0; cy[idx] = 0; dx[idx] = H2; dy[idx] = W2;
		trans[idx] = true;
		G = idx;
		return;
	}

	long double c[4] = { H1, H2, W1, W2 }; sort(c, c + 4);
	long double v1 = c[0], v2 = c[2]; if (H1 == v2 || W1 == v1) swap(v1, v2);
	long double w1 = v1, w2 = v2;
	if (H2 == v1 || W2 == v2) { trans[idx] = false; }
	if (H2 == v2 || W2 == v1) { trans[idx] = true; swap(w1, w2); }

	long double c1 = 0, c2 = 0;
	long double d1 = 0, d2 = 0;
	if (H1 == v1) {
		ax[idx] = 0; ay[idx] = W1 - v2;
		bx[idx] = H1; by[idx] = W1;
		c1 = H1; c2 = W1 - v2;
	}
	else if (W1 == v2) {
		ax[idx] = H1 - v1; ay[idx] = 0;
		bx[idx] = H1; by[idx] = W1;
		c1 = H1 - v1; c2 = W1;
	}
	if (H2 == w1) {
		cx[idx] = 0; cy[idx] = W2 - w2;
		dx[idx] = H2; dy[idx] = W2;
		d1 = H2; d2 = W2 - w2;
	}
	else if (W2 == w2) {
		cx[idx] = H2 - w1; cy[idx] = 0;
		dx[idx] = H2; dy[idx] = W2;
		d1 = H2 - w1; d2 = W2;
	}

	solve(c1, c2, d1, d2, idx + 1);
}

int main() {
	FILE* in = freopen("in1.txt", "r", stdin);
	FILE* out = freopen("out1.txt", "w", stdout);

	// ステップ 1. 入力
	cin >> N; X.resize(N, make_pair(0, 0)); for (int i = 0; i < N; i++) cin >> X[i].first >> X[i].second;
	cin >> M; Y.resize(M, make_pair(0, 0)); for (int i = 0; i < M; i++) cin >> Y[i].first >> Y[i].second;

	// ステップ 2. 最大座標を求める
	long double px = 0, py = 0; for (int i = 0; i < N; i++) { px = max(px, X[i].first); py = max(py, X[i].second); }
	long double qx = 0, qy = 0; for (int i = 0; i < M; i++) { qx = max(qx, Y[i].first); qy = max(qy, Y[i].second); }

	// ステップ 3. 三角形を四角形にする
	if (X.size() == 3) {
		Point V1 = Point{ X[0].first, X[0].second };
		Point V2 = Point{ X[1].first, X[1].second };
		Point V3 = Point{ X[2].first, X[2].second };
		long double U1 = getangle(V3, V1, V2);
		long double U2 = getangle(V1, V2, V3);
		long double U3 = getangle(V2, V3, V1);

		if (U2 <= 89.9L && U3 <= 89.9L) { Point W1 = V1, W2 = V2, W3 = V3; V1 = W1; V2 = W2; V3 = W3; }
		else if (U1 <= 89.9L && U3 <= 89.9L) { Point W1 = V1, W2 = V2, W3 = V3; V1 = W2; V2 = W3; V3 = W1; }
		else if (U1 <= 89.9L && U2 <= 89.9L) { Point W1 = V1, W2 = V2, W3 = V3; V1 = W3; V2 = W1; V3 = W2; }
		
		Point V = getproper(V1, V3, V2);
		Point MV = Div(V + V1, 2.0L);
		Point M2 = Div(V2 + V1, 2.0L);
		Point M3 = Div(V3 + V1, 2.0L);
		Point M1 = M2 - (MV - M2);
		Point M4 = M3 + (M3 - MV);
		cout << "scissors" << endl;
		cout << 0 << " " << 4 << endl;
		printf("3 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", V1.px, V1.py, M2.px, M2.py, MV.px, MV.py);
		printf("3 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", MV.px, MV.py, M3.px, M3.py, V1.px, V1.py);
		printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", MV.px, MV.py, M2.px, M2.py, V2.px, V2.py, V.px, V.py);
		printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", V.px, V.py, V3.px, V3.py, M3.px, M3.py, MV.px, MV.py);
		cout << "tape" << endl;
		cout << 4 << " " << 1 << " " << 2 << " " << 3 << " " << 4 << endl;
		printf("3 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", V2.px, V2.py, M2.px, M2.py, M1.px, M1.py);
		printf("3 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", M4.px, M4.py, M3.px, M3.py, V3.px, V3.py);
		printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", MV.px, MV.py, M2.px, M2.py, V2.px, V2.py, V.px, V.py);
		printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", V.px, V.py, V3.px, V3.py, M3.px, M3.py, MV.px, MV.py);
		printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", V2.px, V2.py, V3.px, V3.py, M4.px, M4.py, M1.px, M1.py);
		px = dst(M1, M4);
		py = dst(M1, V2);
		cout << "tape" << endl;
		cout << 1 << " " << 5 << endl;
		printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", 0.0, 0.0, px, 0.0, px, py, 0.0, py);
		printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", 0.0, 0.0, px, 0.0, px, py, 0.0, py);
	}

	// ステップ 4. 操作を行う
	solve(px, py, qx, qy, 7);

	// ステップ 5. 出力を行う
	cout << "scissors" << endl;
	cout << "6 " << G - 6 << endl;
	for (int i = 7; i <= G; i++) printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", ax[i], ay[i], bx[i], ay[i], bx[i], by[i], ax[i], by[i]);

	cout << "tape" << endl;
	cout << G - 6; for (int i = 7; i <= G; i++) cout << " " << i; cout << endl;
	for (int i = 7; i <= G; i++) {
		if (trans[i] == false) printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", cx[i], cy[i], dx[i], cy[i], dx[i], dy[i], cx[i], dy[i]);
		if (trans[i] == true) printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", dx[i], cy[i], dx[i], dy[i], cx[i], dy[i], cx[i], cy[i]);
	}
	printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", 0.0, 0.0, qx, 0.0, qx, qy, 0.0, qy);
	return 0;
}

Compilation message

scissors.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
scissors.cpp: In function 'int main()':
scissors.cpp:164:99: warning: format '%Lf' expects argument of type 'long double', but argument 2 has type 'double' [-Wformat=]
   printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", 0.0, 0.0, px, 0.0, px, py, 0.0, py);
                                                                                                   ^
scissors.cpp:164:99: warning: format '%Lf' expects argument of type 'long double', but argument 3 has type 'double' [-Wformat=]
scissors.cpp:164:99: warning: format '%Lf' expects argument of type 'long double', but argument 5 has type 'double' [-Wformat=]
scissors.cpp:164:99: warning: format '%Lf' expects argument of type 'long double', but argument 8 has type 'double' [-Wformat=]
scissors.cpp:165:99: warning: format '%Lf' expects argument of type 'long double', but argument 2 has type 'double' [-Wformat=]
   printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", 0.0, 0.0, px, 0.0, px, py, 0.0, py);
                                                                                                   ^
scissors.cpp:165:99: warning: format '%Lf' expects argument of type 'long double', but argument 3 has type 'double' [-Wformat=]
scissors.cpp:165:99: warning: format '%Lf' expects argument of type 'long double', but argument 5 has type 'double' [-Wformat=]
scissors.cpp:165:99: warning: format '%Lf' expects argument of type 'long double', but argument 8 has type 'double' [-Wformat=]
scissors.cpp:182:98: warning: format '%Lf' expects argument of type 'long double', but argument 2 has type 'double' [-Wformat=]
  printf("4 %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf %.6Lf\n", 0.0, 0.0, qx, 0.0, qx, qy, 0.0, qy);
                                                                                                  ^
scissors.cpp:182:98: warning: format '%Lf' expects argument of type 'long double', but argument 3 has type 'double' [-Wformat=]
scissors.cpp:182:98: warning: format '%Lf' expects argument of type 'long double', but argument 5 has type 'double' [-Wformat=]
scissors.cpp:182:98: warning: format '%Lf' expects argument of type 'long double', but argument 8 has type 'double' [-Wformat=]
scissors.cpp:117:8: warning: unused variable 'in' [-Wunused-variable]
  FILE* in = freopen("in1.txt", "r", stdin);
        ^~
scissors.cpp:118:8: warning: unused variable 'out' [-Wunused-variable]
  FILE* out = freopen("out1.txt", "w", stdout);
        ^~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Operation 1 (tape), polygon 0, vertex 0: Equivalent polygons must not change distance of any side by more than 0.001000, got '3.000000' vs '4.000000', error '0.333333'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Operation 1 (tape), polygon 0, vertex 0: Equivalent polygons must not change distance of any side by more than 0.001000, got '312000.000000' vs '195000.000000', error '0.375000'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Operation 1 (tape), polygon 0, vertex 0: Equivalent polygons must not change distance of any side by more than 0.001000, got '3.000000' vs '4.000000', error '0.333333'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 508 KB Operation 1 (tape), polygon 0: Equivalent polygons must have same number of vertices (3 != 4)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Operation 1 (tape), polygon 0, vertex 0: Equivalent polygons must not change cosine of any internal angle by more than 0.001000, got '0.081922' vs '0.429625', error '0.347702'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Operation 1 (tape), polygon 0, vertex 0: Equivalent polygons must not change distance of any side by more than 0.001000, got '3.000000' vs '4.000000', error '0.333333'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Operation 1 (tape), polygon 0, vertex 0: Equivalent polygons must not change distance of any side by more than 0.001000, got '3.000000' vs '4.000000', error '0.333333'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Operation 1 (tape), polygon 0, vertex 0: Equivalent polygons must not change distance of any side by more than 0.001000, got '3.000000' vs '4.000000', error '0.333333'
2 Halted 0 ms 0 KB -