3680: 吊打XXX

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge Submit: 2043  Solved: 732 [Submit][Status][Discuss]

Description

gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。蒟蒻们将 n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同，绳 结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。 不计摩擦，不计 …

hdu 5017 题目链接

题意：给出椭球方程的6的参数 a,b,c,d,e,f 

问椭球上的点到原点(0,0,,0)的最小距离是多少。

思路：感觉难点在于，如何保证搜到的点一直在椭球上。

poj 2069 题目链接

题意：给出n个点，找出包含这n个点的最小半径的外接球。求球的半径。

思路：模拟退火。不过在走的时候，不是随机上下左右前后6个方向走，而是每次往距离当前球心最远的点的方向走。这样才能通过（随机6个方向的写法样例也是可以通过的）

貌似香港赛区的规则和大陆有所不同？

来整理一波。

**D. ****中国大陆赛站及境外赛站的关系。**

(a)** **中国大陆各赛站及香港，北朝鲜赛站同为亚洲East Continent子赛区的一部分。

阅读更多

poj 1385 题目链接

题意：求多边形的重心。

思路：

抄模板（逃

嘛。。三角形的重心是三个点坐标的平均数。。。

多边形的重心其实就是先求三角形的重心然后再加权平均一下就好了。。。权值是面积比。

poj 2420

题意：求多边形费马点，也就是距离所有点的距离之和最小的点。

思路：模拟退火裸题。

关于模拟退火的学习： 模拟退火讲解

我就记住了一句话2333：

**爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。**

**　 模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。**

题目链接

题意：问一个小矩形能否放在一个大矩形中，给定两个矩形的尺寸。

思路：主要是斜着放比较难判断。学弟貌似写了离散化角度旋转。。。我的做法是。。直接考虑对角线。。。因为我认为对角线是最有可能放进去的位置。

poj 1386

题意：n个单词，问能否形成一个串（单词接龙，收尾相连，当且仅当前一个单词的末尾字母和后一个单词的首字母相同）

思路：欧拉路。

关于欧拉路：

(1)**有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通（弱联通，），且所有顶点的入度等于出度。**

(2)有向图G为半欧拉图(存在欧拉路)，当且仅当G的基图连通（弱联通），且存在顶点u的入度比出度大1、v的入度比出度小1，其它所有顶点的入度等于出度。

阅读更多

poj 1383题目链接

题意：一个迷宫图，求最远两点的距离是多少，保证每两个点都是联通的。

思路：树的直径。

  1#include <cstdio>
  2#include <cstring>
  3#include <iostream>
  4#include <algorithm>
  5#include <vector>
  6#include <queue>
  7#include <set>
  8#include <map>
  9#include <string>
 10#include …

poj 1379题目链接

题意：给出一个矩形区域的长宽，给出区域中若干点，问距离所有点的最近距离的最大值是多少。

思路：很容易想到模拟退火。

比赛的时候因为忘记判断矩形边界导致答案错得离谱2333