# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
584874 |
2022-06-28T05:59:50 Z |
반딧불(#8380) |
Fences (JOI18_fences) |
C++17 |
|
1 ms |
212 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct vector2{
double x, y;
vector2(){}
vector2(double x, double y): x(x), y(y){}
vector2 operator+(const vector2 &r)const{
return vector2(x+r.x, y+r.y);
}
vector2 operator-(const vector2 &r)const{
return vector2(x-r.x, y-r.y);
}
vector2 operator*(const double &r)const{
return vector2(x*r, y*r);
}
vector2 operator/(const double &r)const{
return vector2(x/r, y/r);
}
bool operator<(const vector2 &r)const{
return make_pair(x, y) < make_pair(r.x, r.y);
}
double cross(vector2 &r)const{
return x*r.y - y*r.x;
}
double dist(vector2 &r)const{
return sqrt((x-r.x)*(x-r.x)+(y-r.y)*(y-r.y));
}
};
double ccw(vector2 a, vector2 b){
return a.cross(b);
}
double ccw(vector2 a, vector2 b, vector2 c){
return ccw(b-a, c-a);
}
int n;
ll s;
vector2 a, b;
double ans=1e18;
vector<vector2> hull(vector<vector2> vec){
vector<vector2> ret;
sort(vec.begin(), vec.end());
ret.push_back(vec[0]);
sort(vec.begin()+1, vec.end(), [&](vector2 &A, vector2 &B){
return ccw(A, vec[0], B) < 0;
});
for(int i=1; i<(int)vec.size(); i++){
while((int)ret.size() >= 2 && ccw(ret[(int)ret.size()-2], ret.back(), vec[i]) < 0) ret.pop_back();
ret.push_back(vec[i]);
}
return ret;
}
void calc(vector2 a, vector2 b){
vector<vector2> h = hull({a, b, vector2(s, s), vector2(s, -s), vector2(-s, s), vector2(-s, -s)});
double sum = 0;
bool found = 0;
for(int i=0; i<(int)h.size(); i++){
auto A = h[i], B = h[(i+1)%(int)h.size()];
sum += A.dist(B);
if(!found){
if(A.dist(a) < 1e-9 && B.dist(b) < 1e-9) found = 1, sum -= a.dist(b);
else if(A.dist(b) < 1e-9 && B.dist(a) < 1e-9) found = 1, sum -= a.dist(b);
}
}
sum = min(sum, double(s)*8);
ans = min(sum, ans);
}
vector2 getPoint(vector2 a, vector2 b, vector2 targ){
for(int cnt=0; cnt<=1000; cnt++){
vector2 p = (a+a+b)/3, q = (a+b+b)/3;
if(targ.dist(p) < targ.dist(q)) b = q;
else a = p;
}
return a;
}
int main(){
scanf("%d %lld", &n, &s);
scanf("%lf %lf %lf %lf", &a.x, &a.y, &b.x, &b.y);
vector<vector2> endpoints = {a, b};
endpoints.push_back(getPoint(a, b, vector2(s, s)));
endpoints.push_back(getPoint(a, b, vector2(s, -s)));
endpoints.push_back(getPoint(a, b, vector2(-s, s)));
endpoints.push_back(getPoint(a, b, vector2(-s, -s)));
for(auto e1: endpoints) for(auto e2: endpoints) calc(e1, e2);
printf("%.9f", ans);
}
Compilation message
fences.cpp: In function 'int main()':
fences.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d %lld", &n, &s);
| ~~~~~^~~~~~~~~~~~~~~~~~~
fences.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf("%lf %lf %lf %lf", &a.x, &a.y, &b.x, &b.y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |