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
Task F - Yakiniku Optimization Problem
User bgrm
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2684 Byte
Status AC
Exec Time 13 ms
Memory 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
All 00-sample-00, 00-sample-01, 01-handmade-00, 01-handmade-01, 01-handmade-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 01-handmade-10, 01-handmade-11, 02-random-00, 02-random-01, 02-random-02, 02-random-03, 02-random-04, 02-random-05, 02-random-06, 02-random-07, 02-random-08, 02-random-09, 02-random-10, 02-random-11, 02-random-12, 02-random-13, 02-random-14, 02-random-15, 02-random-16, 02-random-17, 02-random-18, 02-random-19, 02-random-20, 02-random-21, 02-random-22, 02-random-23, 02-random-24, 02-random-25, 02-random-26, 02-random-27, 02-random-28, 02-random-29, 02-random-30, 02-random-31, 02-random-32, 02-random-33, 02-random-34, 02-random-35, 02-random-36, 02-random-37, 02-random-38, 02-random-39, 02-random-40, 02-random-41, 02-random-42, 02-random-43, 02-random-44, 02-random-45, 02-random-46, 02-random-47, 02-random-48, 02-random-49, 03-killer-00, 03-killer-01, 03-killer-02
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