Submission #148014

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
148014	2019-08-31 11:14:45	imsifile	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	1114 ms	78588 KiB

squad

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "squad.h"
#include <algorithm>
#include <stdio.h>
using namespace std;
 
typedef long long lld;
 
struct coord {
  lld x, y; int ix;
  bool operator< (const coord& c) const {
    if(x!=c.x) return x<c.x;
    return y<c.y;
  }
} AP[1001001], DP[1001001];
 
int N;
 
lld ccw(coord a, coord b, coord c){ // clockwise < 0
  return (a.x*b.y+b.x*c.y+c.x*a.y) - (a.y*b.x+b.y*c.x+c.y*a.x);
}
 
void makehull(coord *ba, vector<int> &chk, int val, vector<coord> &cvx){
  cvx.clear();
  for(int i=0; i<N; i++){
    int sz;
    if(chk[ba[i].ix]==val) continue;
    while(1){
      sz=cvx.size();
      if(sz<2) break;
      if(ccw(cvx[sz-2], cvx[sz-1], ba[i]) < 0) break;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 19 / 19
• Subtask 2: 28 / 28
• Subtask 3: 53 / 53