Submission #3833

#TimeUsernameProblemLanguageResultExecution timeMemory
3833hyeonjae0310Divide into triangle (kriii1_D)C++98
0 / 1
0 ms1240 KiB
#include <stdio.h> #include <algorithm> #include <vector> using namespace std; typedef struct POINT { pair<int, int> point; int index; }POINT; POINT STD; int CCW(pair<int, int> a, pair<int, int> b, pair<int, int> c) { return (a.first*b.second+b.first*c.second+c.first+a.second)-(a.second*b.first+b.second*c.first+c.second*a.first); } bool pair_compare(POINT a, POINT b) { if(a.point.first != b.point.first) { return (a.point.first < b.point.first); } else { return (a.point.second < b.point.second); } } bool angle_compare(POINT a, POINT b) { return (CCW(STD.point, a.point, b.point) < 0); } int main() { vector<POINT> pt; int N; scanf("%d", &N); pt.resize(3*N); for(int i = 0 ; i < 3*N ; i++) { scanf("%d %d", &pt[i].point.first, &pt[i].point.second); pt[i].index = i+1; } while(!pt.empty()) { sort(pt.begin(), pt.end(), pair_compare); STD = pt[0]; sort(pt.begin()+1, pt.end(), angle_compare); for(int i = 0 ; i < 3 ; i++) { printf("%d ", pt.front().index); pt.erase(pt.begin()); } printf("\n"); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...