QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#391766#3787. 割耳法SSAABBEERR0 11ms3904kbC++202.7kb2024-04-16 19:26:212024-04-16 19:26:21

Judging History

This is the latest submission verdict.

  • [2024-04-16 19:26:21]
  • Judged
  • Verdict: 0
  • Time: 11ms
  • Memory: 3904kb
  • [2024-04-16 19:26:21]
  • Submitted

answer

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define pre(x,a,b) for(int x=a;x>=b;x--)
#define endl "\n"
#define pb push_back
#define ll long long
#define int long long
#define pii pair<ll,ll>
#define psi pair<string, ll>
#define de cout<<1;
#define mem(a,x) memset(a,x,sizeof a)
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int mod1=998244353;
const int mod2=1e9+7;
const int INF=1e18;
const int N = 1e6 + 60;
int number;
int n, idx;
double x[110], y[110];
double calc(int i, int j)
{
    return sqrt(abs(x[i] - x[j]) * abs(x[i] - x[j]) + abs(y[i] - y[j]) * abs(y[i] - y[j]));
}
void solve()
{
    while(scanf("%d", &n) != EOF)
    {
        idx ++ ;
        rep(i, 1, n) scanf("%lf%lf", &x[i], &y[i]);
        double ans = 1e9;
        rep(i, 1, n)
        rep(j, i + 1, n)
        {
            if(x[i] == x[j])
            {
                int f = 0, l = 0, r = 0;
                rep(k, 1, 100)
                {
                    if(k == i || k == j) continue;
                    if(x[k] < x[i]) l ++ ;
                    else if(x[k] > x[i]) r ++ ;
                    else
                    {
                        if(y[k] < min(y[i], y[j]) || y[k] > max(y[i], y[j]))
                        {
                            f = 1;
                            break;
                        }
                    }
                }
                if(l == 0 || r == 0) f = 1;
                if(l > 1 && r > 1) f = 1;
                if(f) continue;
                else ans = min(ans, calc(i, j));
            }
            else
            {
                double k = (y[i] - y[j]) / (x[i] - x[j]);
                double b = y[i] - k * x[i];
                int l = 0, r = 0;
                int f = 0;
                rep(w, 1, n)
                {
                    if(w == i || w == j) continue;
                    double yy = k * x[w] + b;
                    if(y[w] > yy) l ++ ;
                    else if(y[w] < yy) r ++ ;
                    else
                    {
                        if(yy > max(y[i], y[w])) f = 1;
                        if(yy < min(y[i], y[w])) f = 1;
                        if(f) break;
                    }
                }
                if(l == 0 || r == 0) f = 1;
                if(l > 1 && r > 1) f = 1;
                if(f) continue;
                ans = min(ans, calc(i, j));
            }
        }
        printf("Case %d: %.4lf\n", idx, ans);
    }
}
signed main()
{
	//IOS;
	int _;
	//scanf("%d", &_);
	_ = 1;
	while(_ -- )
	{
		number++;
		solve();
	}
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 11ms
memory: 3904kb

input:

22
0 0
100 -5
200 -9
300 -12
400 -14
500 -15
600 -14
700 -12
800 -9
900 -5
1000 0
1000 10
900 15
800 19
700 22
600 24
500 25
400 24
300 22
200 19
100 15
0 10
100
100 -25
200 -49
300 -72
400 -94
500 -115
600 -135
700 -154
800 -172
900 -189
1000 -205
1100 -220
1200 -234
1300 -247
1400 -259
1500 -270
1...

output:

Case 1: 101.1187
Case 2: 124.4026
Case 3: 1254.0000
Case 4: 24.0416
Case 5: 128.8604
Case 6: 128.8604
Case 7: 128.8604
Case 8: 99.0051
Case 9: 32.3883
Case 10: 890.0360
Case 11: 21.3776
Case 12: 75.0600
Case 13: 36.3456
Case 14: 253.6218
Case 15: 47.7074
Case 16: 181.4001
Case 17: 75.4255
Case 18: 2...

result:

wrong answer 1st lines differ - expected: 'Case 1: 1324.5436', found: 'Case 1: 101.1187'