# HDOJ 1007-Quoit Design

HDOJ 1007-Quoit Design

# Quoit Design

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 77740    Accepted Submission(s): 20729

Problem DescriptionHave you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.

Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.

InputThe input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.

OutputFor each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.

Sample Input

2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0

Sample Output

0.71
0.00
0.75

AuthorCHEN, Yue
SourceZJCPC2004
RecommendJGShining   |   We have carefully selected several similar problems for you:  10061009100510081004

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;

struct Point
{
double x_, y_;
Point() :x_(0), y_(0) {};
Point(double x, double y) :x_(x), y_(y) {};
};

bool CmpX(const Point &p1, const Point &p2) {
return p1.x_ < p2.x_;
}

bool CmpY(const Point &p1, const Point &p2) {
return p1.y_ < p2.y_;
}

// 暂时只算距离平方，最后开平方根
double CalDist(const Point &p1, const Point &p2) {
return (p1.x_ - p2.x_)*(p1.x_ - p2.x_) + (p1.y_ - p2.y_)*(p1.y_ - p2.y_);
}

double CalMinDist(vector<Point> &data, int l, int r) {

if (r - l == 2) {
return CalDist(data[l], data[l + 1]);
}
else if (r - l == 3) {
double d1 = CalDist(data[l], data[l + 1]);
double d2 = CalDist(data[l], data[l + 2]);
double d3 = CalDist(data[l + 1], data[l + 2]);
return min(min(d1, d2), d3);
}

int m = l + (r - l) / 2;
int mx = data[m].x_;
double dd = min(CalMinDist(data, l, m), CalMinDist(data, m, r));
double d = sqrt(dd);

vector<Point> rect;
for (int i = l; i < r; ++i) {
if (data[i].x_ > mx - d && data[i].x_ < mx + d) {
rect.push_back(data[i]);
}
}

sort(rect.begin(), rect.end(), CmpY);
for (int i = 0; i < rect.size(); ++i) {
for (int j = i + 1; j < rect.size(); ++j) {
double tmpd = CalDist(rect[i], rect[j]);
if (tmpd > dd)break;
dd = min(dd, tmpd);
}
}

return dd;
}

int main() {
freopen("input.txt", "r", stdin);

int n;
while (scanf("%d", &n)) {
if (n == 0)break;
vector<Point> data(n, Point());
for (int i = 0; i < n; ++i) {
scanf("%lf %lf", &data[i].x_, &data[i].y_);
}
sort(data.begin(), data.end(), CmpX);
printf("%.2lf\n", sqrt(CalMinDist(data, 0, data.size())) / 2);
}

return 0;
}

# 剑指 Offer 04. 二维数组中的查找

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

0 <= n <= 1000

0 <= m <= 1000

class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if(matrix.empty() || matrix[0].empty()) return false;
int n = matrix.size(), m = matrix[0].size();
int i = 0, j = m - 1;
while(i < n && j >= 0) {
if(matrix[i][j] == target) return true;
if(target > matrix[i][j]) ++i;
else --j;
}
return false;
}
};

# LeetCode Range Sum Query – Mutable

LeetCode Range Sum Query – Mutable Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. The update(i, val) function modifies nums by updating the element at index i to val. Example:

Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:
1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

# LeetCode Different Ways to Add Parentheses

241. Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +- and *.

Example 1:

Input: "2-1-1"
Output: [0, 2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2

Example 2:

Input: "2*3-4*5" Output: [-34, -14, -10, -10, 10] Explanation:  (2*(3-(4*5))) = -34  ((2*3)-(4*5)) = -14  ((2*(3-4))*5) = -10  (2*((3-4)*5)) = -10  (((2*3)-4)*5) = 10

class Solution {
private:
int operate(int a, int b, char c)
{
switch (c) {
case ‘+’:
return a + b;
case ‘-‘:
return a – b;
case ‘*’:
return a * b;
}
}
public:
vector<int> diffWaysToCompute(string input)
{
int n = input.size();
vector<int> ans;
bool found = false;
for (int i = 0; i < n; ++i) {
if (input[i] == ‘+’ || input[i] == ‘-‘ || input[i] == ‘*’) {
found = true;
vector<int> lefts = diffWaysToCompute(input.substr(0, i));
vector<int> rights = diffWaysToCompute(input.substr(i + 1));
for (int j = 0; j < lefts.size(); ++j) {
for (int k = 0; k < rights.size(); ++k) {
ans.push_back(operate(lefts[j], rights[k], input[i]));
}
}
}
}
if (!found)
return { atoi(input.c_str()) };
return ans;
}
};

# LeetCode Search a 2D Matrix II

240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]


Given target = 5, return true.

Given target = 20, return false.

LeetCode Search a 2D Matrix基础上改动了一点点，但是难度增加不少。这一次，每行和每列都是递增的，但是这一行的行首元素和上一行的行末元素没有大小关系，这种矩阵有点像从左上角递增到右下角的一个曲面，想象一下。 一种比较笨的办法就是对每一行或者每一列二分搜索，复杂度为O(mlgn)或O(nlgm)。 参考这位大神的介绍，有很多厉害的算法，具体看原博客，这里简单给出其前两个算法的C++实现。 算法1相当于对角二分搜索，是线性复杂度的。搜索从矩阵右上角开始，遇到比当前元素大时，递增行；遇到比当前元素小时，递减列；直到找到相等元素，或者到达矩阵左下角。最坏情况是从右上角走到了左下角，复杂度为O(m+n)。 这种思路的代码如下：

class Solution {
public:
bool searchMatrix(vector<vector<int> >& matrix, int target)
{
if (matrix.size() == 0)
return false;
int m = matrix.size(), n = matrix[0].size();
if (n == 0)
return false;
int i = 0, j = n – 1;
while (i < m && j >= 0) {
while (i < m && matrix[i][j] < target)
++i;
if (i >= m)
return false;
while (j >= 0 && matrix[i][j] > target)
–j;
if (j < 0)
return false;
if (matrix[i][j] == target)
return true;
}
return false;
}
};

class Solution {
public:
bool quadPart(vector<vector<int> >& matrix, int left, int top, int right, int bottom, int target)
{
if (left > right || top > bottom)
return false;
if (target < matrix[left][top] || target > matrix[right][bottom])
return false;
int midrow = left + (right - left) / 2, midcol = top + (bottom - top) / 2;
if (target == matrix[midrow][midcol])
return true;

//if (target > matrix[midrow][midcol]) { // 抛弃左上角
//	return quadPart(matrix, left, midcol + 1, midrow - 1, bottom, target) || // 右上角
//		quadPart(matrix, midrow + 1, top, right, midcol - 1, target) || // 左下角
//		quadPart(matrix, midrow, midcol, right, bottom, target); // 右下角
//}
//else {
//	return quadPart(matrix, left, midcol + 1, midrow - 1, bottom, target) || // 右上角
//		quadPart(matrix, midrow + 1, top, right, midcol - 1, target) || // 左下角
//		quadPart(matrix, left, top, midrow, midcol, target); //左上角
//}

if (target > matrix[midrow][midcol]) { // 抛弃左上角
return quadPart(matrix, left, midcol + 1, midrow, bottom, target) || // 右上角
quadPart(matrix, midrow + 1, top, right, midcol, target) || // 左下角
quadPart(matrix, midrow + 1, midcol + 1, right, bottom, target); // 右下角
}
else {
return quadPart(matrix, left, midcol, midrow - 1, bottom, target) || // 右上角
quadPart(matrix, midrow, top, right, midcol - 1, target) || // 左下角
quadPart(matrix, left, top, midrow - 1, midcol - 1, target); //左上角
}
}
bool searchMatrix(vector<vector<int> >& matrix, int target)
{
if (matrix.size() == 0)
return false;
int m = matrix.size(), n = matrix[0].size();
if (n == 0)
return false;
return quadPart(matrix, 0, 0, m - 1, n - 1, target);
}
};

# LeetCode Pow(x, n)

50. Pow(x, n)

Implement pow(xn), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000


Example 2:

Input: 2.10000, 3
Output: 9.26100


Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25


Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−231, 231 − 1]

class Solution {
public:
double doPow(double x, int n)
{
if (n == 0)
return 1.0;
double v = doPow(x, n / 2);
if (n % 2 == 0)
return v * v;
else
return v * v * x;
}
double myPow(double x, int n)
{
int m = n > 0 ? n : -n;
double ans = doPow(x, m);
return n > 0 ? ans : 1.0 / ans;
}
};

class Solution {
public:
double myPow(double x, int n)
{
if (n == 0)
return 1;
if (n == 1)
return x;
long long m = n; // 先转换为ll，否则n=INT_MIN是有问题
m = m > 0 ? m : -m;
double ans = 1;
while (m) {
if (m & 1)
ans *= x;
m >>= 1;
x = x * x;
}
return n > 0 ? ans : 1 / ans;
}
};

class Solution {
public:
double myPow2(double x, long long m) {
if (x == 0.0)return 0.0;
if (x == 1.0 || m == 0)return 1.0;
if (m == 1)return x;
if (m < 0) return 1.0 / myPow2(x, -m);

if (m % 2 == 1)return x * myPow2(x*x, m >> 1);
else return myPow2(x*x, m >> 1);
}
double myPow(double x, int n) {
return myPow2(x, n);
}
};

# LeetCode Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.


If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

class Solution {
public:
int maxSubArray(vector<int>& nums)
{
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (dp[i – 1] > 0)
dp[i] = dp[i – 1] + nums[i];
else
dp[i] = nums[i];
if (dp[i] > ans)
ans = dp[i];
}
return ans;
}
};

class Solution {
public:
int divide(vector<int>& nums, int left, int right)
{
if (left == right)
return nums[left];
if (left == right – 1)
return max(nums[left] + nums[right], max(nums[left], nums[right]));
int mid = (left + right) / 2;
int lmax = divide(nums, left, mid – 1);
int rmax = divide(nums, mid + 1, right);
int mmax = nums[mid], tmp = nums[mid];
for (int i = mid – 1; i >= left; i–) {
tmp += nums[i];
if (tmp > mmax)
mmax = tmp;
}
tmp = mmax;
for (int i = mid + 1; i <= right; i++) {
tmp += nums[i];
if (tmp > mmax)
mmax = tmp;
}
return max(mmax, max(lmax, rmax));
}
int maxSubArray(vector<int>& nums) { return divide(nums, 0, nums.size() – 1); }
};

class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int max_sum = INT_MIN, cur_sum = 0;
for (int i = 0; i < n; ++i) {
if (cur_sum >= 0) {
cur_sum += nums[i];
}
else {
cur_sum = nums[i];
}
max_sum = max(max_sum, cur_sum);
}
return max_sum;
}
};

# LeetCode Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0


Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

int findKthSmallest(int A[], int m, int B[], int n, int k)
{
assert(m >= 0);
assert(n >= 0);
assert(k > 0);
assert(k <= m + n);
int i = (int)((double)m / (m + n) * (k – 1));
int j = (k – 1) – i;
assert(i >= 0);
assert(j >= 0);
assert(i <= m);
assert(j <= n); // invariant: i + j = k-1 // Note: A[-1] = -INF and A[m] = +INF to maintain invariant
int Ai_1 = ((i == 0) ? INT_MIN : A[i – 1]);
int Bj_1 = ((j == 0) ? INT_MIN : B[j – 1]);
int Ai = ((i == m) ? INT_MAX : A[i]);
int Bj = ((j == n) ? INT_MAX : B[j]);
if (Bj_1 < Ai && Ai < Bj)
return Ai;
else if (Ai_1 < Bj && Bj < Ai)
return Bj;
assert((Ai > Bj && Ai_1 > Bj) || (Ai < Bj && Ai < Bj_1)); // if none of the cases above, then it is either:
if (Ai < Bj) // exclude Ai and below portion // exclude Bj and above portion
return findKthSmallest(A + i + 1, m – i – 1, B, j, k – i – 1);
else /* Bj < Ai */ // exclude Ai and above portion // exclude Bj and below portion
return findKthSmallest(A, i, B + j + 1, n – j – 1, k – j – 1);
}

class Solution {
public:
double findKthSmallest(vector<int>& nums1, vector<int>& nums2, int k) //find kth smallest
{
int m = nums1.size(), n = nums2.size(); //always assume that m is equal or smaller than n
if (m > n)
return findKthSmallest(nums2, nums1, k);
if (m == 0)
return nums2[k – 1];
if (k == 1)
return min(nums1[0], nums2[0]); //divide k into two parts
int i = (int)((double)m / (m + n) * (k – 1));
int j = (k – 1) – i;
int Ai_1 = ((i == 0) ? INT_MIN : nums1[i – 1]);
int Bj_1 = ((j == 0) ? INT_MIN : nums2[j – 1]);
int Ai = ((i == m) ? INT_MAX : nums1[i]);
int Bj = ((j == n) ? INT_MAX : nums2[j]);
if (Bj_1 < Ai && Ai < Bj)
return Ai;
else if (Ai_1 < Bj && Bj < Ai)
return Bj;
if (Ai < Bj) {
vector<int> v1(nums1.begin() + i + 1, nums1.end());
vector<int> v2(nums2.begin(), nums2.begin() + j);
return findKthSmallest(v1, v2, k – i – 1);
}
else if (Ai > Bj) {
vector<int> v1(nums1.begin(), nums1.begin() + i);
vector<int> v2(nums2.begin() + j + 1, nums2.end());
return findKthSmallest(v1, v2, k – j – 1);
}
else
return Ai;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
int total = nums1.size() + nums2.size();
if (total & 0x01)
return findKthSmallest(nums1, nums2, total / 2 + 1);
else
return (findKthSmallest(nums1, nums2, total / 2) + findKthSmallest(nums1, nums2, total / 2 + 1)) / 2;
}
};

O(lgn+lgm)的解法。假设arr1和arr2的中位数分别是arr1[mid1]和arr2[mid2]，如果mid1+mid2<k，说明两个中位数的位置都太小了，第k大的数比较大。如果arr1[mid1]<arr2[mid2]，则mid1左边是这四块中最小的一块，k肯定不在这里，所以可以递归在[mid1+1,end1]和[start2,end2]之间找；arra1[mid1]>arr2[mid2]的情况类似。

class Solution {
private:
int findKth(vector<int>& nums1, int s1, int e1, vector<int>& nums2, int s2, int e2, int k)
{
int len1 = e1 – s1 + 1, len2 = e2 – s2 + 1;
if (len1 > len2)
return findKth(nums2, s2, e2, nums1, s1, e1, k);
if (len1 == 0)
return nums2[s2 + k – 1];
if (k == 1)
return min(nums1[s1], nums2[s2]);
int i = s1 + min(k / 2, len1) – 1, j = s2 + min(k / 2, len2) – 1;
if (nums1[i] > nums2[j])
return findKth(nums1, s1, e1, nums2, j + 1, e2, k – (j – s2 + 1));
else
return findKth(nums1, i + 1, e1, nums2, s2, e2, k – (i – s1 + 1));
}
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
int m = nums1.size(), n = nums2.size();
if ((m + n) % 2) {
return findKth(nums1, 0, m – 1, nums2, 0, n – 1, (m + n) / 2 + 1);
}
else {
return (findKth(nums1, 0, m – 1, nums2, 0, n – 1, (m + n) / 2) + findKth(nums1, 0, m – 1, nums2, 0, n – 1, (m + n) / 2 + 1)) / 2.0;
}
}
};

          left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if (m > n)return findMedianSortedArrays(nums2, nums1);
int low = 0, high = m;
while (low <= high) {
int partition1 = (low + high) / 2;
int partition2 = (m + n + 1) / 2 - partition1;

int maxleft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
int minright1 = (partition1 == m) ? INT_MAX : nums1[partition1];

int maxleft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
int minright2 = (partition2 == n) ? INT_MAX : nums2[partition2];

if (maxleft1 <= minright2 && maxleft2 <= minright1) {
if ((m + n) % 2 == 0) {
int mid1 = maxleft1 > maxleft2 ? maxleft1 : maxleft2;
int mid2 = minright1 < minright2 ? minright1 : minright2;
return (mid1 + mid2) / 2.0;
}
else {
return maxleft1 > maxleft2 ? maxleft1 : maxleft2;
}
}
else if (maxleft1 > minright2) {
high = partition1 - 1;
}
else if (maxleft2 > minright1) {
low = partition1 + 1;
}
}
return 0;
}
};

# hihoCoder 1139-二分·二分答案

hihoCoder 1139-二分·二分答案 #1139 : 二分·二分答案 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在上一回和上上回里我们知道Nettle在玩《艦これ》，Nettle在整理好舰队之后终于准备出海捞船和敌军交战了。 在这个游戏里面，海域是N个战略点(编号1..N)组成，如下图所示 其中红色的点表示有敌人驻扎，猫头像的的点表示该地图敌军主力舰队(boss)的驻扎点，虚线表示各个战略点之间的航线(无向边)。 在游戏中要从一个战略点到相邻战略点需要满足一定的条件，即需要舰队的索敌值大于等于这两点之间航线的索敌值需求。 由于提高索敌值需要将攻击机、轰炸机换成侦察机，舰队索敌值越高，也就意味着舰队的战力越低。 另外在每一个战略点会发生一次战斗，需要消耗1/K的燃料和子弹。必须在燃料和子弹未用完的情况下进入boss点才能与boss进行战斗，所以舰队最多只能走过K条航路。 现在Nettle想要以最高的战力来进攻boss点，所以他希望能够找出一条从起始点(编号为1的点)到boss点的航路，使得舰队需要达到的索敌值最低，并且有剩余的燃料和子弹。 特别说明：两个战略点之间可能不止一条航线，两个相邻战略点之间可能不止一条航线。保证至少存在一条路径能在燃料子弹用完前到达boss点。 提示：你在找什么？ 输入 第1行：4个整数N,M,K,T。N表示战略点数量，M表示航线数量，K表示最多能经过的航路，T表示boss点编号, 1≤N,K≤10,000, N≤M≤100,000 第2..M+1行：3个整数u,v,w，表示战略点u,v之间存在航路，w表示该航路需求的索敌值，1≤w≤1,000,000。 输出 第1行：一个整数，表示舰队需要的最小索敌值。 样例输入 5 6 2 5 1 2 3 1 3 2 1 4 4 2 5 2 3 5 5 4 5 3 样例输出 3

# hihoCoder 1133-二分·二分查找之k小数

hihoCoder 1133-二分·二分查找之k小数 #1133 : 二分·二分查找之k小数 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在上一回里我们知道Nettle在玩《艦これ》，Nettle的镇守府有很多船位，但船位再多也是有限的。Nettle通过捞船又出了一艘稀有的船，但是已有的N(1≤N≤1,000,000)个船位都已经有船了。所以Nettle不得不把其中一艘船拆掉来让位给新的船。Nettle思考了很久，决定随机选择一个k，然后拆掉稀有度第k小的船。 已知每一艘船都有自己的稀有度，Nettle现在把所有船的稀有度值告诉你，希望你能帮他找出目标船。 提示：非有序数组的二分查找之二 输入 第1行：2个整数N,k。N表示数组长度， 第2行：N个整数，表示a[1..N]，保证不会出现重复的数，1≤a[i]≤2,000,000,000。 输出 第1行：一个整数t，表示t在数组中是第k小的数，若K不在数组中，输出-1。 样例输入 10 4 1732 4176 2602 6176 1303 6207 3125 1 1011 6600 样例输出 1732