Submission #1546867

---

Source Code Expand

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>

using namespace std;
long long x_1, y_1, x_2, y_2, sw;
long long N;
long long X[200000], Y[200000];
long long n;
vector<pair<long long, long long> > fountains;
long long a[200000], dp[200000], len;
long long p_min, p_max, p;

int main() {

	scanf("%lld %lld %lld %lld", &x_1, &y_1, &x_2, &y_2);
	scanf("%lld", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lld %lld",&X[i], &Y[i]);
	}

	if (x_1 > x_2) { 
		sw = x_1; x_1 = x_2; x_2 = sw; 
		sw = y_1; y_1 = y_2; y_2 = sw;
	}
	if (y_1 > y_2) {
		y_1 = -y_1;
		y_2 = -y_2;
		for (int i = 0; i < N; i++) {
			Y[i] = -Y[i];
		}
	}

	/*一直線だった時の処理をここら辺に書く*/

	if (x_1 == x_2) {
		/*間に噴水があるか調べる*/
		for (int i = 0; i < N; i++) {
			if (X[i] == x_1 && y_1 < Y[i] && Y[i] < y_2) {
				/*間に噴水がある*/
				printf("%.15Lf\n", (y_2 - y_1) * 100 - 20 + 40 * atan((long double)1));
				return 0;
			}
		}
		/*噴水はない*/
		printf("%lld\n", (y_2 - y_1) * 100);
		return 0;
	}

	if (y_1 == y_2) {
		/*間に噴水があるか調べる*/
		for (int i = 0; i < N; i++) {
			if (Y[i] == y_1 && x_1 < X[i] && X[i] < x_2) {
				/*間に噴水がある*/
				printf("%.15Lf\n",(x_2 - x_1) * 100 - 20 + 40 * atan((long double)1));
				return 0;
			}
		}
		/*噴水はない*/
		printf("%lld\n", (x_2-x_1)*100);
		return 0;
	}

	/*一直線じゃなかった場合*/

	for (int i = 0; i < N; i++) {
		if (x_1 <= X[i] && X[i] <= x_2 && y_1 <= Y[i] && Y[i] <= y_2) {
			fountains.push_back(make_pair(X[i], Y[i]));
		}
	}
	sort(fountains.begin(), fountains.end());
	/*最長増加部分列*/
	len = 0;
	n = fountains.size();
	if (n > 0) {
		for (int i = 0; i < n; i++) {
			a[i] = fountains[i].second;
		}

		len = 1;
		dp[0] = a[0];
		for (int i = 1; i < n; i++) {
			p_min = 0;
			p_max = len;
			while (p_min < p_max) {
				p = (p_min + p_max) / 2;
				if (dp[p] > a[i]) { p_max = p; }
				else { p_min = p + 1; }
			}
			if (p_min == len) { len++; }
			dp[p_min] = a[i];
			for (int j = 0; j < len; j++) {
			}
		}
	}
	/*(x_2-x_1) + (y_2-y_1)個の道を通って、その間にlen個の噴水を通る。
	100 * ((x_2-x_1) + (y_2-y_1))+(- 20 + 5pi) * len
	*/
	if (len <= x_2 - x_1 && len <= y_2 - y_1) {
		printf("%.15Lf\n", 100 * ((x_2 - x_1) + (y_2 - y_1)) + (-20 + 20 * atan((long double)1)) * len);
	}
	else {
		/*この場合を忘れていたっぽい…このときは、len-1個の噴水でショートカットし、1個の噴水で遠回りをする。
		100 * ((x_2-x_1) + (y_2-y_1))+(- 20 + 5pi) * (len-1) - 20 + 10pi
		*/
		printf("%.15Lf\n", 100 * ((x_2 - x_1) + (y_2 - y_1)) + (-20 + 20 * atan((long double)1)) * (len - 1) - 20 + 40 * atan((long double)1));
	}
	
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:19:54: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld %lld", &x_1, &y_1, &x_2, &y_2);
                                                      ^
./Main.cpp:20:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &N);
                   ^
./Main.cpp:22:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&X[i], &Y[i]);
                                  ^

Judge Result