Contest Duration: - (local time) (100 minutes) Back to Home

Submission #10458730

Source Code Expand

Copy
```#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(int)(b); i++)
#define FORD(i, a, b) for (int i=a; i>(int)(b); i--)
#define PPC(x) __builtin_popcount(x)
#define MSB(x) (31 - __builtin_clz(x))
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define ithBit(m, i) ((m) >> (i) & 1)
#define ft first
#define sd second
#define kw(a) ((a) * (a))
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std;

struct Point
{
long double x, y;	int ind;
Point (long double a = 0, long double b = 0, int i = 0)
: x(a), y(b), ind(i) {}

long double operator% 	(const Point& he) 	const
{	return x * he.y - he.x * y;	}

Point operator- (const Point& he)	const
{	return Point(x - he.x, y - he.y, ind);	}

long double len2()	const
{	return x*x + y*y;	}

bool operator< (const Point& he)	const
{
long double ilo = (*this) % he;
if (ilo != 0)			return ilo > 0;
if (y != 0 or he.y != 0)return y < he.y;
return x < he.x;	//	!abs
}
};

const int maxN = 1 << 6;
const long double E = 1e-5;

int x[maxN], y[maxN], z[maxN], n, k;
long double r[maxN];

vector <Point> crcInter(int i, int j)	//assert inter nonEmpty
{
long long dx = x[i] - x[j], dy = y[i] - y[j], d2 = kw(dx) + kw(dy);
double D = sqrt(d2);
double X = (d2 + kw(r[j]) - kw(r[i])) / (2.0 * D);
double Y = sqrt(kw(r[j]) - kw(X));
vector <Point> res({Point(X, Y), Point(X, -Y)});
double c = dx / D, s = dy / D;
FOR(k, 0, 2)
{
res[k] = Point(res[k] % Point(s,c), res[k] % Point(-c,s));
res[k].x += x[j];
res[k].y += y[j];
}
return res;
}

vector <Point> T;

bool check(long double t)
{
T.resize(0);
FOR(i, 0, n)
{
r[i] = t / z[i];
T.pb({x[i], y[i]});
}

FOR(i, 1, n) FOR(j, 0, i)
{
long double R = kw(r[i] + r[j]), R2 = kw(r[i] - r[j]);
long double D = kw(x[i] - x[j]) + kw(y[i] - y[j]);
if (R >= D-E and D >= R2-E)
{
vector <Point> temp = crcInter(i, j);
T.insert(T.end(), ALL(temp));
}
}

for (Point p : T)
{
int cnt = 0;
FOR(i, 0, n)
{
long double dx = p.x - x[i], dy = p.y - y[i], d = kw(dx) + kw(dy);
if (d <= kw(r[i]) + E)
cnt++;
}

if (cnt >= k)
return true;
}

return false;
}

void solve()
{
scanf ("%d%d", &n, &k);

FOR(i, 0, n)
scanf ("%d%d%d", x+i, y+i, z+i);

long double a = 0, b = 1e6;
while (b - a > 1e-6)
{
long double c = (a+b)/2;
check(c) ? b = c : a = c;
}

printf("%.9Lf\n", (a+b)/2);
}

int main()
{
int t;
t = 1;//scanf ("%d", &t);
while (t--)
solve();
return 0;
}

```

#### Submission Info

Submission Time 2020-03-01 22:07:03+0900 F - Yakiniku Optimization Problem bgrm C++14 (GCC 5.4.1) 600 2684 Byte AC 13 ms 384 KB

#### Compile Error

```./Main.cpp: In function ‘bool check(long double)’:
./Main.cpp:75:12: warning: narrowing conversion of ‘x[i]’ from ‘int’ to ‘long double’ inside { } [-Wnarrowing]
T.pb({x[i], y[i]});
^
./Main.cpp:75:18: warning: narrowing conversion of ‘y[i]’ from ‘int’ to ‘long double’ inside { } [-Wnarrowing]
T.pb({x[i], y[i]});
^
./Main.cpp: In function ‘void solve()’:
./Main.cpp:108:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &n, &k);
^
./Main.cpp:111:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d%d", x+i, y+i, z+i);
^
```

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
 AC × 2
 AC × 67
Set Name Test Cases
Sample 00-sample-00, 00-sample-01
Case Name Status Exec Time Memory
00-sample-00 AC 1 ms 256 KB
00-sample-01 AC 1 ms 256 KB
01-handmade-00 AC 1 ms 256 KB
01-handmade-01 AC 1 ms 256 KB
01-handmade-02 AC 2 ms 384 KB
01-handmade-03 AC 11 ms 384 KB
01-handmade-04 AC 12 ms 384 KB
01-handmade-05 AC 10 ms 384 KB
01-handmade-06 AC 7 ms 384 KB
01-handmade-07 AC 6 ms 384 KB
01-handmade-08 AC 10 ms 384 KB
01-handmade-09 AC 10 ms 384 KB
01-handmade-10 AC 1 ms 256 KB
01-handmade-11 AC 1 ms 256 KB
02-random-00 AC 3 ms 384 KB
02-random-01 AC 10 ms 384 KB
02-random-02 AC 3 ms 384 KB
02-random-03 AC 9 ms 384 KB
02-random-04 AC 9 ms 384 KB
02-random-05 AC 3 ms 384 KB
02-random-06 AC 9 ms 384 KB
02-random-07 AC 4 ms 384 KB
02-random-08 AC 8 ms 384 KB
02-random-09 AC 5 ms 384 KB
02-random-10 AC 10 ms 384 KB
02-random-11 AC 8 ms 384 KB
02-random-12 AC 8 ms 384 KB
02-random-13 AC 7 ms 384 KB
02-random-14 AC 8 ms 384 KB
02-random-15 AC 5 ms 384 KB
02-random-16 AC 4 ms 384 KB
02-random-17 AC 2 ms 384 KB
02-random-18 AC 9 ms 384 KB
02-random-19 AC 9 ms 384 KB
02-random-20 AC 8 ms 384 KB
02-random-21 AC 8 ms 384 KB
02-random-22 AC 8 ms 384 KB
02-random-23 AC 12 ms 384 KB
02-random-24 AC 11 ms 384 KB
02-random-25 AC 4 ms 384 KB
02-random-26 AC 6 ms 384 KB
02-random-27 AC 4 ms 384 KB
02-random-28 AC 3 ms 384 KB
02-random-29 AC 7 ms 384 KB
02-random-30 AC 7 ms 384 KB
02-random-31 AC 13 ms 384 KB
02-random-32 AC 3 ms 384 KB
02-random-33 AC 10 ms 384 KB
02-random-34 AC 2 ms 384 KB
02-random-35 AC 9 ms 384 KB
02-random-36 AC 2 ms 384 KB
02-random-37 AC 8 ms 384 KB
02-random-38 AC 2 ms 384 KB
02-random-39 AC 13 ms 384 KB
02-random-40 AC 11 ms 384 KB
02-random-41 AC 6 ms 384 KB
02-random-42 AC 8 ms 384 KB
02-random-43 AC 12 ms 384 KB
02-random-44 AC 11 ms 384 KB
02-random-45 AC 12 ms 384 KB
02-random-46 AC 9 ms 384 KB
02-random-47 AC 4 ms 384 KB
02-random-48 AC 12 ms 384 KB
02-random-49 AC 12 ms 384 KB
03-killer-00 AC 2 ms 384 KB
03-killer-01 AC 2 ms 384 KB
03-killer-02 AC 2 ms 384 KB