QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#370707 | #784. 旋转卡壳 | black_moonrise | 0 | 1ms | 4080kb | C++14 | 4.1kb | 2024-03-29 15:30:59 | 2024-03-29 15:30:59 |
Judging History
你现在查看的是最新测评结果
- [2024-10-16 12:18:36]
- hack成功,自动添加数据
- (/hack/1005)
- [2024-09-24 16:55:39]
- hack成功,自动添加数据
- (/hack/888)
- [2024-07-31 21:52:32]
- hack成功,自动添加数据
- (/hack/764)
- [2024-07-31 21:47:53]
- hack成功,自动添加数据
- (/hack/763)
- [2024-05-30 09:00:15]
- hack成功,自动添加数据
- (/hack/642)
- [2024-03-29 15:30:59]
- 提交
answer
// TO BE TESTED IN: http://acm.hdu.edu.cn/showproblem.php?pid=7278
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
const double eps = 1e-7;
const double pi = acos(-1);
struct point {
double x, y;
point(double X=0, double Y=0) : x(X), y(Y) {}
point operator+(const point &t) {return point(x+t.x, y+t.y);}
point operator-(const point &t) {return point(x-t.x, y-t.y);}
point operator*(const point &t) {return point(x*t.x-y*t.y, x*t.y+y*t.x);}
point operator*(double t) {return point(x*t, y*t);}
point operator/(double t) {return point(x/t, y/t);}
double det(const point &t) const {return x*t.y - y*t.x;}
double dot(const point &t) {return x*t.x + y*t.y;}
double len() {return sqrt(x*x+y*y);}
point dir() {return (*this) / len();}
double rad() const {return atan2(y, x);}
void in() {scanf("%lf%lf", &x, &y);}
void out() {printf("%lf,%lf ", x, y);}
bool operator < (const point &t) const {return MP(x, y) < MP(t.x, t.y);}
/* bool operator < (const point &t) const {
double t = rad() - t.rad();
if (fabs(t) < 0.1) return t < 0;
return det(t) > 0;
} */
};
int sgn(double x) {return x>eps?1:(x<-eps?-1:0);}
bool SxS(point ax, point ay, point bx, point by) {
int fx = sgn((ay-ax).det(bx-ax));
int fy = sgn((ay-ax).det(by-ax));
if (fx*fy > 0) return false; // >= for strict
swap(ax, bx); swap(ay, by);
fx = sgn((ay-ax).det(bx-ax));
fy = sgn((ay-ax).det(by-ax));
if (fx*fy > 0) return false; // >= for strict
return true;
}
bool LpL(point ax, point ay, point bx, point by) {
return fabs((ay-ax).det(by-bx)) > eps;
}
point LxL(point ax, point ay, point bx, point by) {
double t = (bx-ax).det(by-ax) / (ay-ax).det(by-bx);
return ax + (ay-ax) * t;
}
// Assuming x is on line (p, q)
bool PinS(point x, point p, point q) {
// if ((p-x).len() < eps || (q-x).len() < eps) return true;
return (p-x).dot(q-x) < eps; // < -eps for strict
}
vector<point> LxC(point p, point q, point O, double R) {
point x = LxL(p, q, O, O + (q-p)*point(0,1));
vector<point> ret;
double d = (x-O).len();
if (d < R + eps) {
double l = sqrt(max((double)0.0, R*R - d*d));
ret.PB(x - (q-p).dir() * l);
// if (d > R-eps) return ret;
ret.PB(x + (q-p).dir() * l);
}
return ret;
}
vector<point> SxC(point p, point q, point O, double R) {
auto ret0 = LxC(p, q, O, R);
auto ret = ret0; ret.clear();
for (auto x : ret0) if (PinS(x, p, q)) ret.PB(x);
return ret;
}
// A and B are convex polygons in counter-clockwise order
vector<point> Minkowski(vector<point> A, vector<point> B) {
vector<pair<double, point> > V;
int n = A.size();
int m = B.size();
point AO, BO;
for (int _=0; _<2; _++) {
double mn = 100;
for (int i=0; i<n; i++) {
point t = A[(i+1)%n] - A[i];
double r = t.rad();
V.PB(MP(r, t));
if (r < mn) mn = r, AO = A[i];
}
swap(AO, BO); swap(A, B);
}
sort(V.begin(), V.end());
vector<point> C;
point x = AO + BO;
for (auto t : V) C.PB(x), x = x + t.SS;
return C;
}
double tri_area(double x, double y, double z) {
double p=(x+y+z)/2;
return sqrt(p*(p-x)*(p-y)*(p-z));
}
//convex hull
vector<int> construct_ch(vector<point> &a, int coef) { // 1 /\ -1 \/
vector<int> s;
for (int i=0; i<a.size(); i++) {
int sz=s.size();
while (sz>=2 && (a[i]-a[s[sz-2]]).det(a[s[sz-1]]-a[s[sz-2]])*coef<eps){
s.pop_back();
sz--;
}
s.PB(i);
}
return s;
}
vector<int> construct_chull(vector<point> &a) {
vector<int> h1=construct_ch(a,-1), h2=construct_ch(a,1), h;
vector<point> v;
for (auto x : h1) h.PB(x);
for(int i=int(h2.size())-2;i>0;i--) h.PB(h2[i]);
for (auto x : h) v.PB(a[x]);
a = v;
return h;
}
vector<point> V;
int main() {
int n;
scanf("%d", &n);
for (int i=1; i<=n; i++) {
point p;
p.in();
V.PB(p);
}
double ans = 0;
int r = 1;
for (int i=0; i<V.size(); i++) {
ans = max(ans, (V[i] - V[0]).len());
while ((V[(r+1)%V.size()] - V[r]).det(V[(i+1)%V.size()] - V[i]) < 0) {
r = (r+1) % V.size();
ans = max(ans, (V[i] - V[0]).len());
}
}
printf("%.10lf\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4080kb
input:
1000 0 0 -997615 -8573 -1988394 -28911 -2726572 -44296 -3491635 -60392 -4419752 -82814 -5298550 -105946 -5723430 -118453 -6608257 -147267 -7034966 -161982 -7563964 -181682 -8507871 -222865 -9499799 -271846 -10090186 -303547 -10400262 -322989 -10614073 -339725 -11081438 -378596 -11791568 -439127 -127...
output:
274127196.9550098777
result:
wrong answer 1st numbers differ - expected: '274339223.1895614', found: '274127196.9550099', error = '0.0007729'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%