103 lines
2.9 KiB
C++
103 lines
2.9 KiB
C++
|
#include<iostream>
|
||
|
#include<vector>
|
||
|
#include<set>
|
||
|
#include<algorithm>
|
||
|
using namespace std;
|
||
|
|
||
|
class Solution{
|
||
|
public:
|
||
|
struct Point{
|
||
|
int x;
|
||
|
int y;
|
||
|
bool operator<(const Point& other) const{
|
||
|
if (x!=other.x)return x<other.x;
|
||
|
return y < other.y;
|
||
|
}
|
||
|
};
|
||
|
|
||
|
static bool cmp(const Point &a, const Point &b){
|
||
|
return a.x < b.x ||(a.x == b.x && a.y < b.y);
|
||
|
}
|
||
|
static bool cmp1(const Point &a, const Point &b){
|
||
|
return a.y < b.y ||(a.y == b.y && a.x < b.x);
|
||
|
}
|
||
|
void print_vec(set<Point> x){
|
||
|
for(auto e: x){
|
||
|
cout<<'('<<e.x<<','<<e.y<<"), ";
|
||
|
}
|
||
|
cout<<endl;
|
||
|
}
|
||
|
int numIdleDrives(vector<int> x, vector<int> y){
|
||
|
|
||
|
vector<Point> poi;
|
||
|
set<Point> hor;
|
||
|
set<Point> ver;
|
||
|
|
||
|
int n = x.size();
|
||
|
for(int i = 0 ; i < n ; i++){
|
||
|
poi.push_back({x[i], y[i]});
|
||
|
}
|
||
|
sort(poi.begin(), poi.end(), cmp);
|
||
|
int cur_x = poi[0].x;
|
||
|
int sum_x = 0;
|
||
|
Point last_point = poi[0];
|
||
|
hor.insert(last_point);
|
||
|
// horizontal
|
||
|
for(int i = 1 ; i < n ; i++){
|
||
|
Point cur_p = poi[i];
|
||
|
if(cur_p.x == cur_x){
|
||
|
sum_x += 1;
|
||
|
}
|
||
|
else{
|
||
|
if(sum_x >= 2)
|
||
|
hor.insert(last_point);
|
||
|
hor.insert(cur_p);
|
||
|
sum_x = 1;
|
||
|
cur_x = cur_p.x;
|
||
|
}
|
||
|
last_point = cur_p;
|
||
|
}
|
||
|
//vertical
|
||
|
sort(poi.begin(), poi.end(), cmp1);
|
||
|
int cur_y = poi[0].y;
|
||
|
int sum_y = 1;
|
||
|
last_point = poi[0];
|
||
|
ver.insert(last_point);
|
||
|
for(int i = 1 ; i < n ; i++){
|
||
|
Point cur_p = poi[i];
|
||
|
if(cur_p.y == cur_y){
|
||
|
sum_y += 1;
|
||
|
}
|
||
|
else{
|
||
|
if(sum_y >= 2)
|
||
|
ver.insert(last_point);
|
||
|
ver.insert(cur_p);
|
||
|
sum_y = 1;
|
||
|
cur_y = cur_p.y;
|
||
|
}
|
||
|
last_point = cur_p;
|
||
|
}
|
||
|
set<Point> rlt;
|
||
|
for(const auto& point : ver){
|
||
|
rlt.insert(point);
|
||
|
}
|
||
|
for(const auto& point : hor){
|
||
|
rlt.insert(point);
|
||
|
}
|
||
|
|
||
|
return n - rlt.size();
|
||
|
}
|
||
|
};
|
||
|
int main(){
|
||
|
Solution *sol = new Solution();
|
||
|
vector<int>x = {0, 0, 0, 0, 0, 1, 1, 1, 2, -1, -1, -2, -1};
|
||
|
vector<int>y = {-1, 0, 1, 2, -2, 0, 1, -1, 0, 1, -1, 0, 0};
|
||
|
cout<<sol->numIdleDrives(x,y)<<endl;
|
||
|
vector<int>x1 = {1, 1, 1, 2, 2, 2, 2, 3, 3, 3};
|
||
|
vector<int>y1 = {1, 2, 3, 1, 2, 3, 5, 1, 2, 3};
|
||
|
cout<<sol->numIdleDrives(x1,y1)<<endl;
|
||
|
vector<int>x2 = {0, -1,0,0,3,5,4,4,4};
|
||
|
vector<int>y2 = {0,0,1,-1,0,0,1,-1,0};
|
||
|
cout<<sol->numIdleDrives(x2,y2)<<endl;
|
||
|
}
|
||
|
// {0,1},{0,4},{1,0},{2,2},{1,3},{0,4},{2,5},{3,4}
|