oj.uz

Submission #73189

# Submission time Handle Problem Language Result Execution time Memory
73189 2018-08-28T03:49:19 Z KLPP Fences (JOI18_fences) C++14
0 / 100
 3 ms 696 KB 
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<vector>
using namespace std;
#define INF 100000000;
typedef pair<int,int> point;

bool acute(point a, point b, point c){
	a.first-=b.first;
	c.first-=b.first;
	a.second-=b.second;
	c.second-=b.second;
	if(a.first*c.second+a.second*c.first>=0)return true;
	return false;
}
double distpp(point a, point b){
	double ans=(a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
	ans=sqrt(ans);
	return ans;
}
double distpl(point a, point b, point c){
	if(acute(a,b,c)){
		if(acute(a,c,b)){
	double area=a.first*b.second+b.first*c.second+c.first*a.second-a.second*b.first-b.second*c.first-c.second*a.first;
		if(area<0)area=-area;
			//cout<<area<<endl;
			return area/distpp(b,c);
		}
		return distpp(a,c);
	}
	return distpp(a,b);
}
int main(){
	int n,s;
	cin>>n>>s;
	int fences[n][4];
	for(int i=0;i<n;i++)cin>>fences[i][0]>>fences[i][1]>>fences[i][2]>>fences[i][3];
	double d=8*s;
	vector<pair<int,int> >points;
	points.push_back(pair<int,int>(-s,-s));
	points.push_back(pair<int,int>(-s,+s));
	points.push_back(pair<int,int>(+s,+s));
	points.push_back(pair<int,int>(+s,-s));
	for(int i=0;i<4;i++){
		int next=(i+1)%4;
		double can=6*s;
		can+=distpl(points[i],pair<int,int>(fences[i][0],fences[i][1]),pair<int,int>(fences[i][2],fences[i][3]));
		can+=distpl(points[next],pair<int,int>(fences[i][0],fences[i][1]),pair<int,int>(fences[i][2],fences[i][3]));
		d=min(d,can);
		//cout<<can<<endl;
	}
	
	
	cout<<d<<endl;
	


	return 0;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 3 ms 476 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Incorrect 2 ms 696 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 3 ms 476 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Incorrect 2 ms 696 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 3 ms 476 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Incorrect 2 ms 696 KB Output isn't correct
6 Halted 0 ms 0 KB -