首页 > ACM题库 > HDU-杭电 > hdu 2927 A Day at the Races[解题报告]C++
2014
02-23

hdu 2927 A Day at the Races[解题报告]C++

A Day at the Races

问题描述 :

Formula One is the highest class of car racing sports. A typical Formula One season consists of a series of races called “Grands Prix" which constructors like Ferrari, Renault, etc. and others participate with one or more cars driven by the best drivers in the world. During the season, teams compete in two parallel championships: the drivers championship and the teams championship.

In the drivers championship, drivers compete to achieve the maximum total number of points by the end of the season, the rules of the competition states that the top eight drivers at each Grand Prix receive 10,8,6,5,4,3,2,1 points respectively. In case of points tie, the driver with the highest number of first places leads. If still tied, then the highest second places, and so on till the highest 8th places. If still tied, then drivers are sorted lexicographically by their last and then by their first names.

After each race, the points received by each driver are added to his team’s pocket, and at the end of the season the team with the highest number of points wins the teams championship. To add excitement to the season, team sponsors are allowed to buy drivers from other teams even within the same season. In case of points tie between teams, teams are sorted lexicographically by their names. In this problem, you are given data of a formula one season and you’re asked to process these data according to the rules above to determine both the drivers and teams standings.

输入:

Your program will be tested on one or more data-sets, each representing a Formula One season. All input lines are 255 characters or less. Studying the sample I/O you’ll discover that the first line of each season has an integer N , where 0 < N < 32 and representing the number of Grands Prix in that season. For each Grand Prix, the name of the Grand Prix appears on a line by itself (maximum length is 64 characters) followed by a table of the first name, last name and team name of the top eight drivers, from 1 to 8, in that Grand Prix. Each of the first and last names is a sequence of printable ASCII characters, no longer than 12 characters, and contains no spaces. Each team name is a sequence of printable ASCII characters, no longer than 18 characters, and may contain spaces (but no leading or trailing spaces.) Each team name is followed by a single period `.’ which is not part of the name. Trailing white space may follow. A line of three -’s follows the listing of each Grand Prix. The last line of the input file contains a single zero.

输出:

Your program will be tested on one or more data-sets, each representing a Formula One season. All input lines are 255 characters or less. Studying the sample I/O you’ll discover that the first line of each season has an integer N , where 0 < N < 32 and representing the number of Grands Prix in that season. For each Grand Prix, the name of the Grand Prix appears on a line by itself (maximum length is 64 characters) followed by a table of the first name, last name and team name of the top eight drivers, from 1 to 8, in that Grand Prix. Each of the first and last names is a sequence of printable ASCII characters, no longer than 12 characters, and contains no spaces. Each team name is a sequence of printable ASCII characters, no longer than 18 characters, and may contain spaces (but no leading or trailing spaces.) Each team name is followed by a single period `.’ which is not part of the name. Trailing white space may follow. A line of three -’s follows the listing of each Grand Prix. The last line of the input file contains a single zero.

样例输入:

2
FORMULA 1 Gran Premio Telefonica de Espana 2006
Pos  Driver                    Team
1    Fernando Alonso           Renault.
2    Michael Schumacher        Ferrari.
3    Giancarlo Fisichella      Renault.
4    Felipe Massa              Ferrari.
5    Kimi Raikkonen            McLaren-Mercedes.
6    Jenson Button             Honda.
7    Rubens Barrichello        Honda.
8    Nick Heidfeld             Sauber-BMW.
---
FORMULA 1 Grand Prix de Monaco 2006
Pos  Driver                    Team
1    Fernando Alonso           Renault.
2    Jaun-Pablo Montoya        McLaren-Mercedes.
3    David Coulthard           RBR-Ferrari.
4    Rubens Barrichello        Honda.
5    Michael Schumacher        Ferrari.
6    Giancarlo Fisichella      Renault.
7    Nick Heidfeld             Sauber-BMW.
8    Ralf Schumacher           Toyota.
---
0

样例输出:

Season 1:
Drivers Standing:
Fernando Alonso           20
Michael Schumacher        12
Giancarlo Fisichella      9
Jaun-Pablo Montoya        8
Rubens Barrichello        7
David Coulthard           6
Felipe Massa              5
Kimi Raikkonen            4
Jenson Button             3
Nick Heidfeld             3
Ralf Schumacher           1

Teams Standing:
Renault                   29
Ferrari                   17
McLaren-Mercedes          12
Honda                     10
RBR-Ferrari               6
Sauber-BMW                3
Toyota                    1


AC代码:

/*
 * Author: OpenLegend
 * Created Time:  2010-8-27 15:42:05
 * File Name: J.cpp
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

const double eps = 1e-8;
const double pi = acos(-1.0);

int sgn(double d) {
    if (d > eps)
        return 1;
    if (d < -eps)
        return -1;
    return 0;
}

struct point {
    double x, y;
    point(double _x = 0, double _y = 0): x(_x), y(_y) {
    }
    void input() {
        scanf("%lf%lf", &x, &y);
    }
    double len() const {
        return sqrt(x * x + y * y);
    }
    point trunc(double l) const {
        double r = l / len();
        return point(x * r, y * r);
    }
    point rotate_left() const {
        return point(-y, x);
    }
    point rotate_right() const {
        return point(y, -x);
    }
};

bool operator==(const point& p1, const point& p2) {
    return sgn(p1.x - p2.x) == 0 && sgn(p1.y - p2.y) == 0;
}

bool operator<(const point& p1, const point& p2) {
    return sgn(p1.x - p2.x) == 0 ? sgn(p1.y - p2.y) < 0 : p1.x < p2.x;
}

point operator+(const point& p1, const point& p2) {
    return point(p1.x + p2.x, p1.y + p2.y);
}

point operator-(const point& p1, const point& p2) {
    return point(p1.x - p2.x, p1.y - p2.y);
}

double operator^(const point& p1, const point& p2) {
    return p1.x * p2.x + p1.y * p2.y;
}

double operator*(const point& p1, const point& p2) {
    return p1.x * p2.y - p1.y * p2.x;
}

bool get_intersection(const point& p1, const point& p2, const point& p3, const point& p4, point& c) {
    double d1 = (p2 - p1) * (p3 - p1), d2 = (p2 - p1) * (p4 - p1);
    if (sgn(d1 - d2) == 0)
        return false;
    c = point((p3.x * d2 - p4.x * d1) / (d2 - d1), (p3.y * d2 - p4.y * d1) / (d2 - d1));
    return true;
}

int n;
point p[16];
pair<int, double> dp[1 << 11][11][11], ans;

bool solve();
void compute();

int main() {
    while (solve());
    return 0;
}

bool solve() {
    scanf("%d", &n);
    if (n == 0)
        return false;
    for (int i = 0; i < n; ++i)
        p[i].input();
    sort(p, p + n);
    n = unique(p, p + n) - p;
    if (n < 2) {
        puts("0 0.0000000");
        return true;
    }
    compute();
    printf("%d %.8lf\n", ans.first, ans.second);
    return true;
}

void compute() {
    for (int i = 0; i < (1 << n); ++i)
        for (int j = 0; j < n; ++j)
            for (int k = 0; k < n; ++k)
                dp[i][j][k].first = 256;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j)
                continue;
            dp[(1 << i) | (1 << j)][i][j] = make_pair(0, (p[j] - p[i]).len());
        }
    }
    for (int i = 0; i < (1 << n); ++i) {
        for (int x = 0; x < n; ++x) {
            if (((i >> x) & 1) == 0)
                continue;
            for (int y = 0; y < n; ++y) {
                if (y == x || ((i >> y) & 1) == 0)
                    continue;
                if (dp[i][x][y].first == 256)
                    continue;
                pair<int, double>& cur = dp[i][x][y];
                for (int j = 0; j < n; ++j) {
                    if (((i >> j) & 1) == 1)
                        continue;
                    pair<int, double>& res = dp[i | (1 << j)][y][j];
                    if (sgn((p[j] - p[x]) * (p[y] - p[x])) == 0) {
                        if (sgn((p[j] - p[y]) ^ (p[x] - p[y])) < 0) {
                            res = min(res, make_pair(cur.first, cur.second + (p[j] - p[y]).len()));
                        } else {
                            res = min(res, make_pair(cur.first + 1, cur.second + (p[j] - p[y]).len()));
                        }
                    } else {
                        res = min(res, make_pair(cur.first + 1, cur.second + (p[j] - p[y]).len()));
                    }
                }
                for (int j = 0; j < n; ++j) {
                    if (((i >> j) & 1) == 1)
                        continue;
                    for (int k = 0; k < n; ++k) {
                        if (k == j || ((i >> k) & 1) == 1)
                            continue;
                        pair<int, double>& res = dp[i | (1 << j) | (1 << k)][j][k];
                        point c;
                        if (get_intersection(p[x], p[y], p[j], p[k], c)) {
                            if (sgn((p[x] - p[y]) ^ (c - p[y])) < 0 && sgn((p[k] - p[j]) ^ (c - p[j])) < 0) {
                                res = min(res, make_pair(cur.first + 1, cur.second + (c - p[y]).len() + (c - p[k]).len()));
                            }
                        }
                    }
                }
            }
        }
    }
    ans.first = 256;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            ans = min(ans, dp[(1 << n) - 1][i][j]);
}

 


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks