QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#370707#784. 旋转卡壳black_moonrise0 1ms4080kbC++144.1kb2024-03-29 15:30:592024-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]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4080kb
  • [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%