Submission #3602578


Source Code Expand

#include "iostream"
#include "vector"
#include "string"
#include "algorithm"

using namespace std;


//(x,y)が直線方向に対し左か右か
//+が左手
int linetoLR(long a, long b, long c, long d, long x, long y)
{
  long check = (c - a) * (y - b) - (d - b) * (x - a);
  int res;
  if (check > 0)
  {
    res = 1;
  }
  else
  if (check < 0)
  {
    res = -1;
  }
  else
  {
    res = 0;
  }
  return res;
}

int main()
{
  int n;
  cin >> n;
  string s[5010];
  long x[5010], y[5010];
  for (int i = 0; i < n; i++)
  {
    cin >> s[i] >> x[i] >> y[i];
  }
  int m;
  cin >> m;
  string t[5010];
  int tnum[5010];
  for (size_t i = 0; i < m; i++)
  {
    cin >> t[i];
    for (int j = 0; j < n; j++)
    {
      if (t[i] == s[j])
      {
        tnum[i] = j;
      }
    }
  }

  tnum[m] = tnum[0];

  int check;
  int index = 0;
  string sans[5010];
  long xans[5010];
  for (int i = 0; i < n; i++)
  {
    check = 0;
    for (int j = 0; j < m; j++)
    {
      check += linetoLR(x[tnum[j]], y[tnum[j]], x[tnum[j + 1]], y[tnum[j + 1]], x[i], y[i]);
    }
    if (abs(check) == m)
    {
      sans[index] = s[i];
      xans[index] = x[i];
      index++;
    }
  }
  for (int i = -10000; i < 10001; i++)
  {
    for (int j = 0; j < index; j++)
    {
      if (xans[j] == i)
      {
        cout << sans[j] << endl;
      }
    }
  }
}

Submission Info

Submission Time
Task G - 志なかばで死んだ勇者の名は…
User shirara
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1425 Byte
Status AC
Exec Time 83 ms
Memory 896 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 20
Set Name Test Cases
All 00_sample_00.txt, 00_sample_01.txt, 10_min_00.txt, 10_min_01.txt, 10_min_02.txt, 20_max_00.txt, 20_max_01.txt, 20_max_02.txt, 90_random_00.txt, 90_random_01.txt, 90_random_02.txt, 90_random_03.txt, 90_random_04.txt, 90_random_05.txt, 90_random_06.txt, 90_random_07.txt, 90_random_08.txt, 90_random_09.txt, 99_final_00.txt, yuha-c88-j.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 384 KB
00_sample_01.txt AC 1 ms 384 KB
10_min_00.txt AC 1 ms 384 KB
10_min_01.txt AC 1 ms 384 KB
10_min_02.txt AC 1 ms 384 KB
20_max_00.txt AC 82 ms 896 KB
20_max_01.txt AC 60 ms 768 KB
20_max_02.txt AC 83 ms 896 KB
90_random_00.txt AC 68 ms 768 KB
90_random_01.txt AC 79 ms 768 KB
90_random_02.txt AC 70 ms 768 KB
90_random_03.txt AC 52 ms 640 KB
90_random_04.txt AC 51 ms 640 KB
90_random_05.txt AC 59 ms 768 KB
90_random_06.txt AC 80 ms 768 KB
90_random_07.txt AC 71 ms 768 KB
90_random_08.txt AC 81 ms 768 KB
90_random_09.txt AC 43 ms 640 KB
99_final_00.txt AC 41 ms 896 KB
yuha-c88-j.txt AC 41 ms 768 KB