QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#391766 | #3787. 割耳法 | SSAABBEERR | 0 | 11ms | 3904kb | C++20 | 2.7kb | 2024-04-16 19:26:21 | 2024-04-16 19:26:21 |
Judging History
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'