QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#554043#2754. Playing the SlotsTenshi#AC ✓0ms3980kbC++202.5kb2024-09-09 02:43:102024-09-09 02:43:11

Judging History

你现在查看的是最新测评结果

  • [2024-09-09 02:43:11]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3980kb
  • [2024-09-09 02:43:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
 
#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;
 
inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const double eps=1e-8, pi=acos(-1);

/*start-----------------------------------------------------------------*/
struct Point{
    double x, y;
    Point(double x=0, double y=0): x(x), y(y){}
};

typedef Point Vector;

Vector operator + (Vector A, Vector B){return Vector(A.x+B.x, A.y+B.y);}
Vector operator - (Vector A, Vector B){return Vector(A.x-B.x, A.y-B.y);}
Vector operator * (Vector A, Vector B){return Vector(A.x*B.x, A.y*B.y);}
Vector operator / (Vector A, Vector B){return Vector(A.x/B.x, A.y/B.y);}

int sign(double x){
    if(fabs(x)<eps) return 0;
    return x<0? -1: 1;
}

int cmp(double x, double y){
    return sign(x-y);
}

bool operator < (const Point &a, const Point &b) {
    return sign(a.x-b.x)<0 || sign(sign(a.x-b.x)==0 && sign(a.y-b.y)<0);
}

double dot(Vector A, Vector B){
    return A.x*B.x+A.y*B.y;
}

double cross(Vector A, Vector B){
    return A.x*B.y-A.y*B.x;
}

double get_length(Vector A){
    return sqrt(dot(A, A));
}

double get_dist(Point a, Point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double get_angle(Vector A, Vector B){
    return acos(dot(A, B)/get_length(A)/get_length(B));
}

double area(Point a, Point b, Point c){
    return cross(b-a, c-a);
}

double displ(Point a, Point b, Point c){
	double s=abs(area(a, b, c));
	double d=get_dist(b, c);
	return s/d;
}

Point pt[110];
int n;

bool chk(Point a, Point b, Point c){
	return !cmp( (c.y-a.y)*(b.x-a.x), (b.y-a.y)*(c.x-a.x) );
}

signed main(){
	cin>>n;
	int tot=0;
	rep(i, 1, n){
		++tot;
		cin>>pt[tot].x>>pt[tot].y;
		if(tot>1 && !cmp(pt[tot].x, pt[tot-1].x) && !cmp(pt[tot].y, pt[tot-1].y)) tot--;	
		if(tot>=3 && chk(pt[tot], pt[tot-1], pt[tot-2])) pt[tot-1]=pt[tot], tot--;
	}
	n=tot;
	// debug(n);
	
	double res=1e9;
	
	rep(j, 1, n){
		int k=j%n+1;
		double t=0;
		rep(i, 1, n){
			t=max(t, displ(pt[i], pt[j], pt[k]));
		}
		res=min(res, t);
	}
	printf("%.2lf\n", res);
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3912kb

input:

3
0 0
0.71 3.54
4.21 4.21

output:

2.00

result:

ok found '2.00000', expected '2.00000', error '0.00000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

6
10 12.5
10 17.5
15 20
20 17.5
20 12.5
15 10

output:

8.94

result:

ok found '8.94000', expected '8.94000', error '0.00000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

4
0 0
0 100
100 100
100 0

output:

100.00

result:

ok found '100.00000', expected '100.00000', error '0.00000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3976kb

input:

4
1 0
0 1
99 100
100 99

output:

1.41

result:

ok found '1.41000', expected '1.41000', error '0.00000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

4
2 0
0 2
99 100
100 99

output:

2.83

result:

ok found '2.83000', expected '2.83000', error '0.00000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3980kb

input:

3
0 0
5 5
10 0

output:

5.00

result:

ok found '5.00000', expected '5.00000', error '0.00000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3964kb

input:

10
54.44 9.94
45.31 0.07
36.32 3.49
34.34 13.93
35.50 16.18
52.75 16.05
52.82 15.95
53.45 14.81
53.93 13.60
53.97 13.47

output:

16.04

result:

ok found '16.04000', expected '16.04000', error '0.00000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

15
98.34 9.49
87.82 2.39
86.71 2.31
80.18 3.73
73.72 10.47
73.17 11.92
72.80 13.33
73.98 22.17
75.56 24.63
77.91 26.94
81.85 29.04
84.35 29.64
84.77 29.69
85.89 29.77
99.12 20.87

output:

24.79

result:

ok found '24.79000', expected '24.79000', error '0.00000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

20
71.22 9.66
50.91 0.82
44.41 4.02
41.88 6.42
39.00 10.96
38.75 11.55
39.60 26.64
39.67 26.76
46.12 33.53
51.42 35.67
52.93 35.95
54.59 36.11
58.75 35.82
64.67 33.56
64.76 33.51
68.01 30.98
70.07 28.55
71.82 25.48
72.63 23.28
73.29 19.90

output:

31.90

result:

ok found '31.90000', expected '31.90000', error '0.00000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

3
40.59 32.45
31.93 37.62
80.95 83.34

output:

9.69

result:

ok found '9.69000', expected '9.69000', error '0.00000'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3964kb

input:

4
97.90 71.66
56.29 86.94
80.06 99.72
98.47 81.35

output:

20.19

result:

ok found '20.19000', expected '20.19000', error '0.00000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

5
30.40 64.53
21.97 71.91
26.62 93.86
34.39 97.04
35.90 97.19

output:

9.54

result:

ok found '9.54000', expected '9.54000', error '0.00000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

6
63.18 16.04
59.65 22.57
59.17 24.28
72.77 48.54
82.24 49.38
97.79 38.03

output:

22.29

result:

ok found '22.29000', expected '22.29000', error '0.00000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

7
41.78 68.84
31.24 68.90
20.75 81.66
32.63 99.50
39.53 99.73
46.93 96.21
46.95 96.20

output:

23.04

result:

ok found '23.04000', expected '23.04000', error '0.00000'