Submission #2181500


Source Code Expand

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>

using namespace std;
typedef long long LL;
typedef double T;
typedef pair<T,T> P;
// difference
P operator-(const P& lhs, const P& rhs)
{
	return P(lhs.first-rhs.first,lhs.second-rhs.second);
}

P operator+(const P& lhs, const P& rhs)
{
	return P(lhs.first+rhs.first, lhs.second+rhs.second);
}

// scalar product
P operator*(T t, P p){
	return P(t*p.first,t*p.second);
}

P operator/(P p, T t){
	return P(p.first/t,p.second/t);
}

// cross product
T Cross(const P& lhs, const P& rhs)
{
	return lhs.first*rhs.second-lhs.second*rhs.first;
}

// inner product 
T Dot(const P& lhs, const P& rhs)
{
	return lhs.first*rhs.first+lhs.second*rhs.second;
}

// square of distance
T Dist2(const P& lhs, const P& rhs){
	return Dot(lhs-rhs,lhs-rhs);
}


// intersection of line
bool IntersectLineParam(P s0, P e0, P s1, P e1, T& t0, T& t1)
{
	P a=s1-s0;
	P v=e0-s0;
	P w=s1-e1;
	T det=Cross(v,w);
	if(det == 0){
		return false;
	}
	t0=Cross(a,w)/det;
	t1=Cross(v,a)/det;
	return true;
}
int main() {
	LL N;
	double sx,gx;
	cin >> N;
	cin >> sx >> gx;
	P l0,l1,r0,r1;
	deque<P> ls;
	deque<P> rs;
	double ret=0;
	for(int i=0;i<=N;i++){
		double l,r;
		cin >> l >> r;
		if(i==0){
			l=r=sx;
		}
		else if(i==N){
			l=r=gx;
		}
		ls.push_back(P(l,i));
		rs.push_back(P(r,i));
		while(ls.size()>=3){
			P u=ls[ls.size()-2]-ls[ls.size()-3];
			P v=ls[ls.size()-1]-ls[ls.size()-3];
			if(Cross(u,v)<=0){
				ls.erase(ls.end()-2);
			}
			else{
				break;
			}
		}
		while(rs.size()>=3){
			P u=rs[rs.size()-2]-rs[rs.size()-3];
			P v=rs[rs.size()-1]-rs[rs.size()-3];
			if(Cross(u,v)>=0){
				rs.erase(rs.end()-2);
			}
			else{
				break;
			}
		}
		if(ls.size()>=2&&rs.size()>=2){
			P u=ls[1]-ls[0];
			P v=rs[1]-rs[0];
			if(Cross(u,v)>=0){
				if(ls[1].second<rs[1].second){
					ret+=sqrt(Dot(u,u));
					//cout << "a: " << u.first << ", " << u.second << endl;
					ls.pop_front();
					rs[0]=ls[0];
				}
				else if(ls[1].second==rs[1].second){
					ret+=sqrt(Dot(u,u));
					ls.pop_front();
					rs.pop_front();
				}
				else{
					ret+=sqrt(Dot(v,v));
					//cout << "b: " << v.first << ", " << v.second << endl;
					rs.pop_front();
					ls[0]=rs[0];
				}
			}
		}
		//cout << i << ", " << ret << endl;
	}
	for(int i=1;i<ls.size();i++){
		//cout << "c: " << u.first << ", " << u.second << endl;
		ret+=sqrt(Dist2(ls[i],ls[i-1]));
	}
	cout.precision(20);
	cout << ret << endl;
	return 0;
}

Submission Info

Submission Time
Task A - センター採点
User kenimo
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2978 Byte
Status WA
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
WA × 30
Set Name Test Cases
All 00_sample1.txt, 00_sample2.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_all_1.txt, 02_all_2.txt, 02_all_3.txt, 02_all_4.txt, 03_mini_1.txt, 03_mini_2.txt, 03_mini_3.txt, 03_mini_4.txt
Case Name Status Exec Time Memory
00_sample1.txt WA 1 ms 256 KB
00_sample2.txt WA 1 ms 256 KB
01_rnd_00.txt WA 1 ms 256 KB
01_rnd_01.txt WA 1 ms 256 KB
01_rnd_02.txt WA 1 ms 256 KB
01_rnd_03.txt WA 1 ms 256 KB
01_rnd_04.txt WA 1 ms 256 KB
01_rnd_05.txt WA 1 ms 256 KB
01_rnd_06.txt WA 1 ms 256 KB
01_rnd_07.txt WA 1 ms 256 KB
01_rnd_08.txt WA 1 ms 256 KB
01_rnd_09.txt WA 1 ms 256 KB
01_rnd_10.txt WA 1 ms 256 KB
01_rnd_11.txt WA 1 ms 256 KB
01_rnd_12.txt WA 1 ms 256 KB
01_rnd_13.txt WA 1 ms 256 KB
01_rnd_14.txt WA 1 ms 256 KB
01_rnd_15.txt WA 1 ms 256 KB
01_rnd_16.txt WA 1 ms 256 KB
01_rnd_17.txt WA 1 ms 256 KB
01_rnd_18.txt WA 1 ms 256 KB
01_rnd_19.txt WA 1 ms 256 KB
02_all_1.txt WA 1 ms 256 KB
02_all_2.txt WA 1 ms 256 KB
02_all_3.txt WA 1 ms 256 KB
02_all_4.txt WA 1 ms 256 KB
03_mini_1.txt WA 1 ms 256 KB
03_mini_2.txt WA 1 ms 256 KB
03_mini_3.txt WA 1 ms 256 KB
03_mini_4.txt WA 1 ms 256 KB