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 |
|
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 |