UVa 12085 - Mobile Casanova

Accepted date: 2015-02-27
Ranking (as of 2015-02-27): 25 out of 308
Language: C++

/*
  UVa 12085 - Mobile Casanova

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_12085_Mobile_Casanova.cpp
*/

#include <cstdio>
#include <cstdlib>
#include <cstring>

int main()
{
  for (int case_nr = 1; ; case_nr++) {
    int N;
    scanf("%d", &N);
    if (!N)
      break;
    printf("Case %d:\n", case_nr);
    const int nr_chars_max = 15;
    char ss[nr_chars_max + 1], es[nr_chars_max + 1], s[nr_chars_max + 1];
    scanf("%s", ss);
    strcpy(es, ss);
    int sn = atoi(ss), en = sn, n;
    while (--N) {
      scanf("%s", s);
      n = atoi(s);
      if (n != en + 1) {
        const char *pss = ss, *pes = es;
        for ( ; *pss && *pss == *pes; pss++, pes++)
          ;
        if (*pes)
          printf("%s-%s\n", ss, pes);
        else
          printf("%s\n", ss);
        strcpy(ss, s);
        strcpy(es, s);
        sn = en = n;
      }
      else {
        strcpy(es, s);
        en = n;
      }
    }
    const char *pss = ss, *pes = es;
    for ( ; *pss && *pss == *pes; pss++, pes++)
      ;
    if (*pes)
      printf("%s-%s\n", ss, pes);
    else
      printf("%s\n", ss);
    putchar('\n');
  }
  return 0;
}

UVa 12504 - Updating a Dictionary

Accepted date: 2015-02-25
Language: C++

/*
  UVa 12504 - Updating a Dictionary

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_12504_Updating_a_Dictionary.cpp
*/

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

void get_dictionary(const string& s, map<string, string>& dic)
{
  const char* p = s.c_str();
  p++;
  if (*p == '}')
    return;
  while (true) {
    const char* q = p;
    while (*p != ':')
      p++;
    string key = string(q, p - q);
    q = ++p;
    while (*p != ',' && *p != '}')
      p++;
    dic[key] = string(q, p - q);
    if (*p++ == '}')
      break;
  }
}

int main()
{
  int T;
  cin >> T;
  while (T--) {
    map<string, string> old_dic, new_dic;
    string s;
    cin >> s;
    get_dictionary(s, old_dic);
    cin >> s;
    get_dictionary(s, new_dic);
    vector<string> added, removed, changed;
    map<string, string>::const_iterator oi = old_dic.begin(), oe = old_dic.end(),
      ni = new_dic.begin(), ne = new_dic.end();
    for ( ; oi != oe && ni != ne; ) {
      if (oi->first < ni->first) {
        removed.push_back(oi->first);
        ++oi;
      }
      else if (oi->first > ni->first) {
        added.push_back(ni->first);
        ++ni;
      }
      else {
        if (oi->second != ni->second)
          changed.push_back(oi->first);
        ++oi; ++ni;
      }
    }
    for ( ; oi != oe; ++oi)
      removed.push_back(oi->first);
    for ( ; ni != ne; ++ni)
      added.push_back(ni->first);
    if (added.empty() && removed.empty() && changed.empty())
      cout << "No changes\n";
    else {
      if (!added.empty()) {
        for (size_t i = 0; i < added.size(); i++)
          cout << ((i) ? ',' : '+') << added[i];
        cout << endl;
      }
      if (!removed.empty()) {
        for (size_t i = 0; i < removed.size(); i++)
          cout << ((i) ? ',' : '-') << removed[i];
        cout << endl;
      }
      if (!changed.empty()) {
        for (size_t i = 0; i < changed.size(); i++)
          cout << ((i) ? ',' : '*') << changed[i];
        cout << endl;
      }
    }
    cout << endl;
  }
  return 0;
}

UVa 12100 - Printer Queue

Accepted date: 2015-02-24
Language: C++

/*
  UVa 12100 - Printer Queue

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_12100_Printer_Queue.cpp
*/

#include <iostream>
#include <queue>
using namespace std;

struct job {
  int i_;
  int p_;

  job() {}
  job(int i, int p) : i_(i), p_(p) {}
};

int main()
{
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    priority_queue<int> pq;
    queue<job> q;
    for (int i = 0; i < n; i++) {
      int p;
      cin >> p;
      pq.push(p);
      q.push(job(i, p));
    }
    int nr = 0;
    while (true) {
      int p = pq.top(); pq.pop();
      job j;
      while (true) {
        j = q.front(); q.pop();
        if (j.p_ == p)
          break;
        q.push(j);
      }
      nr++;
      if (j.i_ == m)
        break;
    }
    cout << nr << endl;
  }
  return 0;
}

UVa 1583 - Digit Generator

Accepted date: 2015-02-08
Ranking (as of 2015-02-08): 147 out of 493
Language: C++

/*
  UVa 1583 - Digit Generator

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_1583_Digit_Generator.cpp
*/

#include <cstdio>

const int N_max = 100000;
int generators[N_max + 1];

int digit_sum(int n)
{
  int s = n;
  do {
    s += n % 10;
    n /= 10;
  } while (n);
  return s;
}

int main()
{
  for (int i = 1; i <= N_max; i++) {
    int ds = digit_sum(i);
    if (ds <= N_max && !generators[ds])
      generators[ds] = i;
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    int N;
    scanf("%d", &N);
    printf("%d\n", generators[N]);
  }
  return 0;
}

UVa 148 - Anagram checker

Accepted date: 2015-02-06
Ranking (as of 2015-02-06): 252 out of 938
Language: C++

/*
  UVa 148 - Anagram checker

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_148_Anagram_checker.cpp
*/

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cstring>
#include <cctype>
using namespace std;

const int nr_words_max = 2000, nr_letters = 26;

struct word {
  bool found_; // true if this word was found in the phrases
  string s_;
  int length_;
  int freqs_[nr_letters];

  bool operator<(const word& w) const {return s_ < w.s_;}
};

vector<word> words(nr_words_max + 1);

string phrases;
int afreqs[nr_letters], pfreqs[nr_letters];
int anagram_words[nr_words_max]; // indices of words that consist of an anagram

void anagram(int n, int wi, int awn, int pfn, int afn)
{
  int i;
  if (pfn == afn) {
    for (i = 0; i < awn; i++)
      if (!words[anagram_words[i]].found_)
        break;
    if (i < awn) { // some words are not original ones
      cout << phrases << " = ";
      for (int i = 0; i < awn; i++) {
        if (i)
          cout << ' ';
        cout << words[anagram_words[i]].s_;
      }
      cout << endl;
    }
  }
  else if (wi < n) {
    const word& w = words[wi];
    if (w.length_ + afn <= pfn) {
      for (i = 0; i < nr_letters; i++) {
        if (afreqs[i] + w.freqs_[i] > pfreqs[i])
          break;
        afreqs[i] += w.freqs_[i];
      }
      if (i == nr_letters) {
        anagram_words[awn] = wi;
        anagram(n, wi + 1, awn + 1, pfn, afn + w.length_);
      }
      for (i--; i >= 0; i--)
        afreqs[i] -= w.freqs_[i];
    }
    anagram(n, wi + 1, awn, pfn, afn);
  }
}

int main()
{
  int n = 0;
  while (true) {
    word& w = words[n];
    getline(cin, w.s_);
    if (w.s_ == "#")
      break;
    w.length_ = w.s_.length();
    memset(w.freqs_, 0, sizeof(w.freqs_));
    for (const char* p = w.s_.c_str(); *p; p++)
      w.freqs_[*p - 'A']++;
    n++;
  }
  words.resize(n);
  while (true) {
    getline(cin, phrases);
    if (phrases == "#")
      break;
    for (int i = 0; i < n; i++)
      words[i].found_ = false;
    int pfn = 0;
    memset(pfreqs, 0, sizeof(pfreqs));
    for (const char *p = phrases.c_str(), *q = NULL; ; p++) {
      if (isupper(*p)) {
        pfreqs[*p - 'A']++;
        if (!q)
          q = p;
        pfn++;
      }
      else {
        word w;
        w.s_ = string(q, p - q);
        pair<vector<word>::iterator, vector<word>::iterator> bounds =
          equal_range(words.begin(), words.end(), w);
        for (vector<word>::iterator i = bounds.first, e = bounds.second; i != e; ++i)
          i->found_ = true;
        q = NULL;
      }
      if (!*p)
        break;
    }
    memset(afreqs, 0, sizeof(afreqs));
    anagram(n, 0, 0, pfn, 0);
  }
  return 0;
}

UVa 10173 - Smallest Bounding Rectangle

Accepted date: 2015-02-01
Ranking (as of 2015-02-01): 180 out of 431
Language: C++

/*
  UVa 10173 - Smallest Bounding Rectangle

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10173_Smallest_Bounding_Rectangle.cpp
*/

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <limits>
#include <cmath>
using namespace std;

const double epsilon = numeric_limits<float>::epsilon();

struct point {
  double x, y;

  point() : x(0.0), y(0.0) {}
  point(double _x, double _y) : x(_x), y(_y) {}
  point(const point &p) : x(p.x), y(p.y) {}
  bool operator==(const point& p) const {return x == p.x && y == p.y;}
};

ostream& operator<<(ostream& os, const point& p)
{
  os << '(' << p.x << ", " << p.y << ')';
  return os;
}

bool left_lower(const point& p1, const point& p2)
{
  if (p1.x < p2.x)
    return true;
  else if (p1.x > p2.x)
    return false;
  else if (p1.y < p2.y)
    return true;
  else
    return false;
}

void sort_and_remove_duplicates(vector<point>& points,
  bool (*compare)(const point&, const point&) /* = left_lower */)
{
  sort(points.begin(), points.end(), compare);
    // sort the points in leftmost-lowest order
  for (vector<point>::iterator i = points.begin(); i != points.end(); ) {
    // remove the duplicate points
    vector<point>::iterator j = i;
    j++;
    if (j != points.end() && *i == *j)
      i = points.erase(i);
    else
      i++;
  }
}

double signed_triangle_area(const point& a, const point& b, const point& c)
{
  return
    (a.x * b.y - a.y * b.x + a.y * c.x - a.x * c.y + b.x * c.y - c.x * b.y) / 2.0;
}

bool collinear(const point& a, const point& b, const point& c)
{
  return fabs(signed_triangle_area(a, b, c)) <= epsilon;
}

double euclidean_distance(const point& a, const point& b)
{
  double dx = a.x - b.x, dy = a.y - b.y;
  return sqrt(dx * dx + dy * dy);
}

bool ccw(const point& a, const point& b, const point& c)
{
  // see if the point c is to the left of a -> b (or, a - b - c are counterclockwise)
  return signed_triangle_area(a, b, c) > epsilon;
}

bool cw(const point& a, const point& b, const point& c)
{
  // see if the point c is to the right of a -> b (or, a - b - c are clockwise)
  return signed_triangle_area(a, b, c) < -epsilon;
}

struct smaller_angle {
  const point& first;

  smaller_angle(const point& _first) : first(_first) {}
  bool operator() (const point& p1, const point& p2) const;
};

bool smaller_angle::operator() (const point& p1, const point& p2) const
{
  if (collinear(first, p1, p2))
    return euclidean_distance(first, p1) <= euclidean_distance(first, p2);
  else
    return ccw(first, p1, p2);
}

int convex_hull(vector<point>& points, vector<point>& hull)
{
  sort_and_remove_duplicates(points, left_lower);
    // sort the points in leftmost-lowest order
  vector<point>::iterator i = points.begin();
  i++;
  sort(i, points.end(), smaller_angle(points[0]));
    // sort the second and later points in increasing angular order
  hull.resize(points.size());
  hull[0] = points[0]; hull[1] = points[1];
  int j = 1;
  for (int i = 2; i < points.size(); ) {
    if (cw(hull[j - 1], hull[j], points[i]))
      j--; // remove hulll[j]
    else {
      if (!collinear(hull[j - 1], hull[j], points[i]))
        j++;
      hull[j] = points[i++];
    }
  }
  if (cw(hull[j - 1], hull[j], points[0]))
    ;
  else
    j++;
  hull.resize(j);
#ifdef DEBUG
  for (int i = 0; i < hull.size(); i++) {
    if (i)
      cout << ' ';
    cout << hull[i];
  }
  cout << endl;
#endif
  return hull.size();
}

bool point_in_hull(point& p, const vector<point>& hull)
{
  int n = hull.size();
  for (int i = 0; i < n; i++)
    if (cw(hull[i], hull[(i + 1) % n], p))
      return false;
  return true;
}

double polygon_area(const vector<point>& polygon)
{
  double area = 0.0;
  for (int i = 0; i < polygon.size(); i++) {
    int j = (i + 1) % polygon.size();
    area += polygon[i].x * polygon[j].y - polygon[j].x * polygon[i].y;
  }
  return area / 2.0;
}

point rotate_point(const point& o, const point& p, double angle)
  // rotate p by angle around o
{
  if (fabs(angle) < epsilon)
    angle = 0.0;
  double x = p.x - o.x, y = p.y - o.y;
  return  point(o.x + x * cos(angle) - y * sin(angle),
    o.y + x * sin(angle) + y * cos(angle));
}

double min_bounding_rectangle_area(const vector<point>& hull)
{
/*
  for each edge of the convex hull:
    compute the edge orientation.
    rotate the convex hull using this orientation.
    calculate the bounding rectangle area with 
      min/max of x/y of the rotated convex hull.
*/
  int n = hull.size();
  double min_area = numeric_limits<double>::max();
  for (int i = 0; i < n; i++) {
    int j = (i + 1) % n;
    double angle = atan2(hull[j].y - hull[i].y, hull[j].x - hull[i].x);
    double min_x = hull[i].x, min_y = hull[i].y, max_x = hull[i].x, max_y = hull[i].y;
    for ( ; j != i; j = (j + 1) % n) {
      point p = rotate_point(hull[i], hull[j], -angle);
      min_x = min(min_x, p.x); min_y = min(min_y, p.y);
      max_x = max(max_x, p.x); max_y = max(max_y, p.y);
    }
#ifdef DEBUG
    cout << angle << ' ' << point(min_x, min_y) <<
      ' ' << point(max_x, max_y) << endl;
#endif
    min_area = min(min_area, (max_x - min_x) * (max_y - min_y));
  }
  return min_area;
}

int main()
{
  const int n_max = 1000;
  vector<point> points(n_max);
  while (true) {
    int n;
    cin >> n;
    if (!n)
      break;
    points.resize(n);
    for (int i = 0; i < n; i++)
      cin >> points[i].x >> points[i].y;
    double area = 0.0;
    if (n > 2) {
      vector<point> hull(n);
      convex_hull(points, hull);
      area = min_bounding_rectangle_area(hull);
    }
    cout << fixed << setprecision(4) << area << endl;
  }
  return 0;
}