Ideone.com

download

copy

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
 
using namespace std;
 
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
 
#define INF 1.0E+9
struct point {double x,y;};
 
int M,N;
point P[110];
point pin[110];
 
int sz;
int st[10010];
 
void add(int x){
	st[sz] = x;
	sz++;
	if(sz >= 2 && st[sz-1] == st[sz-2]) sz -= 2;
}
 
int K;
double x[10010],y[10010];
int sign[10010];
double dp[10010];
 
void add2(point P, int type){
	if(K > 0 && x[K-1] == P.x){
		sign[K-1] = 0;
	} else {
		x[K] = P.x;
		y[K] = P.y;
		sign[K] = type;
		K++;
	}
}
 
double calc_dp(void){
	int i,j;
 
	dp[0] = 0.0;
 
	for(i=1;i<K;i++){
		dp[i] = INF;
		double high = INF, low = -INF;
 
		for(j=i-1;j>=0;j--){
			if((x[j] < x[j+1]) != (x[i-1] < x[i])) break;
 
			double c = (y[i] - y[j]) / (x[i] - x[j]);
			if(x[i-1] < x[i]){
				if(sign[j] >= 0) high = min(high, c);
				if(sign[j] <= 0) low = max(low, c);
			} else {
				if(sign[j] <= 0) high = min(high, c);
				if(sign[j] >= 0) low = max(low, c);
			}
 
			if(high < low) break;
 
			if(low <= c && c <= high){
				double tmp = dp[j] + sqrt((x[i]-x[j]) * (x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j]));
				dp[i] = min(dp[i], tmp);
			}
		}
	}
 
	return dp[K-1];
}
 
double func(void){
	int i,j;
 
	sz = 0;
	REP(i,M-1){
		point Q = P[i], R = P[i+1];
		REP(j,N) if(Q.x < pin[j].x && pin[j].x < R.x){
			double y = Q.y + (R.y - Q.y) / (R.x - Q.x) * (pin[j].x - Q.x);
			if(y < pin[j].y) add(j); else add(j+N);
		}
		for(j=N-1;j>=0;j--) if(R.x < pin[j].x && pin[j].x < Q.x){
			double y = Q.y + (R.y - Q.y) / (R.x - Q.x) * (pin[j].x - Q.x);
			if(y < pin[j].y) add(j); else add(j+N);
		}
	}
 
	K = 0;
	add2(P[0], 0);
	REP(i,sz) add2(pin[st[i] % N], ((st[i] < N) ? -1 : 1));
	add2(P[M-1], 0);
 
	calc_dp();
	return dp[K-1];
}
 
point rotate(point P){
	double x = P.x * cos(0.01) - P.y * sin(0.01);
	double y = P.x * sin(0.01) + P.y * cos(0.01);
	point Q = {x, y};
	return Q;
}
 
int main(void){
	int i,j;
 
	while(cin >> M >> N){
		if(M == 0 && N == 0) break;
 
		REP(i,M) cin >> P[i].x >> P[i].y;
		REP(i,N) cin >> pin[i].x >> pin[i].y;
 
		REP(i,M) P[i] = rotate(P[i]);
		REP(i,N) pin[i] = rotate(pin[i]);
		REP(i,N) REP(j,N-1) if(pin[j].x > pin[j+1].x) swap(pin[j], pin[j+1]);
 
		double ans = func();
		printf("%.9f\n", ans);
	}
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPGZzdHJlYW0+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxmdW5jdGlvbmFsPgojaW5jbHVkZSA8dXRpbGl0eT4KI2luY2x1ZGUgPGJpdHNldD4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGN0aW1lPgojaW5jbHVkZSA8Y3N0ZGlvPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgUkVQKGksbikgZm9yKChpKT0wOyhpKTwoaW50KShuKTsoaSkrKykKI2RlZmluZSBzbnVrZShjLGl0cikgZm9yKF9fdHlwZW9mKChjKS5iZWdpbigpKSBpdHI9KGMpLmJlZ2luKCk7aXRyIT0oYykuZW5kKCk7aXRyKyspCgojZGVmaW5lIElORiAxLjBFKzkKc3RydWN0IHBvaW50IHtkb3VibGUgeCx5O307CgppbnQgTSxOOwpwb2ludCBQWzExMF07CnBvaW50IHBpblsxMTBdOwoKaW50IHN6OwppbnQgc3RbMTAwMTBdOwoKdm9pZCBhZGQoaW50IHgpewoJc3Rbc3pdID0geDsKCXN6Kys7CglpZihzeiA+PSAyICYmIHN0W3N6LTFdID09IHN0W3N6LTJdKSBzeiAtPSAyOwp9CgppbnQgSzsKZG91YmxlIHhbMTAwMTBdLHlbMTAwMTBdOwppbnQgc2lnblsxMDAxMF07CmRvdWJsZSBkcFsxMDAxMF07Cgp2b2lkIGFkZDIocG9pbnQgUCwgaW50IHR5cGUpewoJaWYoSyA+IDAgJiYgeFtLLTFdID09IFAueCl7CgkJc2lnbltLLTFdID0gMDsKCX0gZWxzZSB7CgkJeFtLXSA9IFAueDsKCQl5W0tdID0gUC55OwoJCXNpZ25bS10gPSB0eXBlOwoJCUsrKzsKCX0KfQoKZG91YmxlIGNhbGNfZHAodm9pZCl7CglpbnQgaSxqOwoJCglkcFswXSA9IDAuMDsKCQoJZm9yKGk9MTtpPEs7aSsrKXsKCQlkcFtpXSA9IElORjsKCQlkb3VibGUgaGlnaCA9IElORiwgbG93ID0gLUlORjsKCQkKCQlmb3Ioaj1pLTE7aj49MDtqLS0pewoJCQlpZigoeFtqXSA8IHhbaisxXSkgIT0gKHhbaS0xXSA8IHhbaV0pKSBicmVhazsKCQkJCgkJCWRvdWJsZSBjID0gKHlbaV0gLSB5W2pdKSAvICh4W2ldIC0geFtqXSk7CgkJCWlmKHhbaS0xXSA8IHhbaV0pewoJCQkJaWYoc2lnbltqXSA+PSAwKSBoaWdoID0gbWluKGhpZ2gsIGMpOwoJCQkJaWYoc2lnbltqXSA8PSAwKSBsb3cgPSBtYXgobG93LCBjKTsKCQkJfSBlbHNlIHsKCQkJCWlmKHNpZ25bal0gPD0gMCkgaGlnaCA9IG1pbihoaWdoLCBjKTsKCQkJCWlmKHNpZ25bal0gPj0gMCkgbG93ID0gbWF4KGxvdywgYyk7CgkJCX0KCQkJCgkJCWlmKGhpZ2ggPCBsb3cpIGJyZWFrOwoJCQkKCQkJaWYobG93IDw9IGMgJiYgYyA8PSBoaWdoKXsKCQkJCWRvdWJsZSB0bXAgPSBkcFtqXSArIHNxcnQoKHhbaV0teFtqXSkgKiAoeFtpXS14W2pdKSArICh5W2ldLXlbal0pICogKHlbaV0teVtqXSkpOwoJCQkJZHBbaV0gPSBtaW4oZHBbaV0sIHRtcCk7CgkJCX0KCQl9Cgl9CgkKCXJldHVybiBkcFtLLTFdOwp9Cgpkb3VibGUgZnVuYyh2b2lkKXsKCWludCBpLGo7CgkKCXN6ID0gMDsKCVJFUChpLE0tMSl7CgkJcG9pbnQgUSA9IFBbaV0sIFIgPSBQW2krMV07CgkJUkVQKGosTikgaWYoUS54IDwgcGluW2pdLnggJiYgcGluW2pdLnggPCBSLngpewoJCQlkb3VibGUgeSA9IFEueSArIChSLnkgLSBRLnkpIC8gKFIueCAtIFEueCkgKiAocGluW2pdLnggLSBRLngpOwoJCQlpZih5IDwgcGluW2pdLnkpIGFkZChqKTsgZWxzZSBhZGQoaitOKTsKCQl9CgkJZm9yKGo9Ti0xO2o+PTA7ai0tKSBpZihSLnggPCBwaW5bal0ueCAmJiBwaW5bal0ueCA8IFEueCl7CgkJCWRvdWJsZSB5ID0gUS55ICsgKFIueSAtIFEueSkgLyAoUi54IC0gUS54KSAqIChwaW5bal0ueCAtIFEueCk7CgkJCWlmKHkgPCBwaW5bal0ueSkgYWRkKGopOyBlbHNlIGFkZChqK04pOwoJCX0KCX0KCQoJSyA9IDA7CglhZGQyKFBbMF0sIDApOwoJUkVQKGksc3opIGFkZDIocGluW3N0W2ldICUgTl0sICgoc3RbaV0gPCBOKSA/IC0xIDogMSkpOwoJYWRkMihQW00tMV0sIDApOwoJCgljYWxjX2RwKCk7CglyZXR1cm4gZHBbSy0xXTsKfQoKcG9pbnQgcm90YXRlKHBvaW50IFApewoJZG91YmxlIHggPSBQLnggKiBjb3MoMC4wMSkgLSBQLnkgKiBzaW4oMC4wMSk7Cglkb3VibGUgeSA9IFAueCAqIHNpbigwLjAxKSArIFAueSAqIGNvcygwLjAxKTsKCXBvaW50IFEgPSB7eCwgeX07CglyZXR1cm4gUTsKfQoKaW50IG1haW4odm9pZCl7CglpbnQgaSxqOwoJCgl3aGlsZShjaW4gPj4gTSA+PiBOKXsKCQlpZihNID09IDAgJiYgTiA9PSAwKSBicmVhazsKCQkKCQlSRVAoaSxNKSBjaW4gPj4gUFtpXS54ID4+IFBbaV0ueTsKCQlSRVAoaSxOKSBjaW4gPj4gcGluW2ldLnggPj4gcGluW2ldLnk7CgkJCgkJUkVQKGksTSkgUFtpXSA9IHJvdGF0ZShQW2ldKTsKCQlSRVAoaSxOKSBwaW5baV0gPSByb3RhdGUocGluW2ldKTsKCQlSRVAoaSxOKSBSRVAoaixOLTEpIGlmKHBpbltqXS54ID4gcGluW2orMV0ueCkgc3dhcChwaW5bal0sIHBpbltqKzFdKTsKCQoJCWRvdWJsZSBhbnMgPSBmdW5jKCk7CgkJcHJpbnRmKCIlLjlmXG4iLCBhbnMpOwoJfQoJCglyZXR1cm4gMDsKfQo=

Compilation error #stdin compilation error #stdout 0s 0KB

stdin

copy

Standard input is empty

compilation info

Main.java:1: error: illegal character: \35
#include <iostream>
^
Main.java:1: error: class, interface, or enum expected
#include <iostream>
         ^
Main.java:2: error: illegal character: \35
#include <sstream>
^
Main.java:3: error: illegal character: \35
#include <fstream>
^
Main.java:4: error: illegal character: \35
#include <string>
^
Main.java:5: error: illegal character: \35
#include <vector>
^
Main.java:6: error: illegal character: \35
#include <deque>
^
Main.java:7: error: illegal character: \35
#include <queue>
^
Main.java:8: error: illegal character: \35
#include <stack>
^
Main.java:9: error: illegal character: \35
#include <set>
^
Main.java:10: error: illegal character: \35
#include <map>
^
Main.java:11: error: illegal character: \35
#include <algorithm>
^
Main.java:12: error: illegal character: \35
#include <functional>
^
Main.java:13: error: illegal character: \35
#include <utility>
^
Main.java:14: error: illegal character: \35
#include <bitset>
^
Main.java:15: error: illegal character: \35
#include <cmath>
^
Main.java:16: error: illegal character: \35
#include <cstdlib>
^
Main.java:17: error: illegal character: \35
#include <ctime>
^
Main.java:18: error: illegal character: \35
#include <cstdio>
^
Main.java:22: error: illegal character: \35
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
^
Main.java:22: error: class, interface, or enum expected
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
        ^
Main.java:22: error: class, interface, or enum expected
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
                           ^
Main.java:22: error: class, interface, or enum expected
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
                                        ^
Main.java:23: error: illegal character: \35
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
^
Main.java:23: error: class, interface, or enum expected
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
                                                               ^
Main.java:23: error: class, interface, or enum expected
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
                                                                              ^
Main.java:25: error: illegal character: \35
#define INF 1.0E+9
^
Main.java:26: error: class, interface, or enum expected
struct point {double x,y;};
                         ^
Main.java:28: error: class, interface, or enum expected
int M,N;
^
Main.java:29: error: class, interface, or enum expected
point P[110];
^
Main.java:30: error: class, interface, or enum expected
point pin[110];
^
Main.java:32: error: class, interface, or enum expected
int sz;
^
Main.java:33: error: class, interface, or enum expected
int st[10010];
^
Main.java:35: error: class, interface, or enum expected
void add(int x){
^
Main.java:37: error: class, interface, or enum expected
	sz++;
	^
Main.java:38: error: class, interface, or enum expected
	if(sz >= 2 && st[sz-1] == st[sz-2]) sz -= 2;
	^
Main.java:39: error: class, interface, or enum expected
}
^
Main.java:42: error: class, interface, or enum expected
double x[10010],y[10010];
^
Main.java:43: error: class, interface, or enum expected
int sign[10010];
^
Main.java:44: error: class, interface, or enum expected
double dp[10010];
^
Main.java:46: error: class, interface, or enum expected
void add2(point P, int type){
^
Main.java:49: error: class, interface, or enum expected
	} else {
	^
Main.java:51: error: class, interface, or enum expected
		y[K] = P.y;
		^
Main.java:52: error: class, interface, or enum expected
		sign[K] = type;
		^
Main.java:53: error: class, interface, or enum expected
		K++;
		^
Main.java:54: error: class, interface, or enum expected
	}
	^
Main.java:60: error: class, interface, or enum expected
	dp[0] = 0.0;
	^
Main.java:62: error: class, interface, or enum expected
	for(i=1;i<K;i++){
	^
Main.java:62: error: class, interface, or enum expected
	for(i=1;i<K;i++){
	        ^
Main.java:62: error: class, interface, or enum expected
	for(i=1;i<K;i++){
	            ^
Main.java:64: error: class, interface, or enum expected
		double high = INF, low = -INF;
		^
Main.java:66: error: class, interface, or enum expected
		for(j=i-1;j>=0;j--){
		^
Main.java:66: error: class, interface, or enum expected
		for(j=i-1;j>=0;j--){
		          ^
Main.java:66: error: class, interface, or enum expected
		for(j=i-1;j>=0;j--){
		               ^
Main.java:69: error: class, interface, or enum expected
			double c = (y[i] - y[j]) / (x[i] - x[j]);
			^
Main.java:70: error: class, interface, or enum expected
			if(x[i-1] < x[i]){
			^
Main.java:72: error: class, interface, or enum expected
				if(sign[j] <= 0) low = max(low, c);
				^
Main.java:73: error: class, interface, or enum expected
			} else {
			^
Main.java:75: error: class, interface, or enum expected
				if(sign[j] >= 0) low = max(low, c);
				^
Main.java:76: error: class, interface, or enum expected
			}
			^
Main.java:80: error: class, interface, or enum expected
			if(low <= c && c <= high){
			^
Main.java:82: error: class, interface, or enum expected
				dp[i] = min(dp[i], tmp);
				^
Main.java:83: error: class, interface, or enum expected
			}
			^
Main.java:88: error: class, interface, or enum expected
}
^
Main.java:93: error: class, interface, or enum expected
	sz = 0;
	^
Main.java:94: error: class, interface, or enum expected
	REP(i,M-1){
	^
Main.java:96: error: class, interface, or enum expected
		REP(j,N) if(Q.x < pin[j].x && pin[j].x < R.x){
		^
Main.java:98: error: class, interface, or enum expected
			if(y < pin[j].y) add(j); else add(j+N);
			^
Main.java:98: error: class, interface, or enum expected
			if(y < pin[j].y) add(j); else add(j+N);
			                         ^
Main.java:99: error: class, interface, or enum expected
		}
		^
Main.java:100: error: class, interface, or enum expected
		for(j=N-1;j>=0;j--) if(R.x < pin[j].x && pin[j].x < Q.x){
		          ^
Main.java:100: error: class, interface, or enum expected
		for(j=N-1;j>=0;j--) if(R.x < pin[j].x && pin[j].x < Q.x){
		               ^
Main.java:102: error: class, interface, or enum expected
			if(y < pin[j].y) add(j); else add(j+N);
			^
Main.java:102: error: class, interface, or enum expected
			if(y < pin[j].y) add(j); else add(j+N);
			                         ^
Main.java:103: error: class, interface, or enum expected
		}
		^
Main.java:107: error: class, interface, or enum expected
	add2(P[0], 0);
	^
Main.java:108: error: class, interface, or enum expected
	REP(i,sz) add2(pin[st[i] % N], ((st[i] < N) ? -1 : 1));
	^
Main.java:109: error: class, interface, or enum expected
	add2(P[M-1], 0);
	^
Main.java:111: error: class, interface, or enum expected
	calc_dp();
	^
Main.java:112: error: class, interface, or enum expected
	return dp[K-1];
	^
Main.java:113: error: class, interface, or enum expected
}
^
Main.java:117: error: class, interface, or enum expected
	double y = P.x * sin(0.01) + P.y * cos(0.01);
	^
Main.java:118: error: class, interface, or enum expected
	point Q = {x, y};
	^
Main.java:119: error: class, interface, or enum expected
	return Q;
	^
Main.java:120: error: class, interface, or enum expected
}
^
Main.java:125: error: class, interface, or enum expected
	while(cin >> M >> N){
	^
Main.java:128: error: class, interface, or enum expected
		REP(i,M) cin >> P[i].x >> P[i].y;
		^
Main.java:129: error: class, interface, or enum expected
		REP(i,N) cin >> pin[i].x >> pin[i].y;
		^
Main.java:131: error: class, interface, or enum expected
		REP(i,M) P[i] = rotate(P[i]);
		^
Main.java:132: error: class, interface, or enum expected
		REP(i,N) pin[i] = rotate(pin[i]);
		^
Main.java:133: error: class, interface, or enum expected
		REP(i,N) REP(j,N-1) if(pin[j].x > pin[j+1].x) swap(pin[j], pin[j+1]);
		^
Main.java:135: error: class, interface, or enum expected
		double ans = func();
		^
Main.java:136: error: class, interface, or enum expected
		printf("%.9f\n", ans);
		^
Main.java:137: error: class, interface, or enum expected
	}
	^
Main.java:140: error: class, interface, or enum expected
}
^
95 errors

stdout

copy

Standard output is empty

https://ideone.com/xk1y6J

language:

Java (HotSpot 12)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language