Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int flag;
- struct pt {
- int x,y,z;
- };
- bool cmp(pt a, pt b) {
- return a.x < b.x || (a.x == b.x && a.y < b.y);
- }
- int area(pt a, pt b, pt c) {
- return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
- }
- vector<int> convex_hull(vector<pt>& a) {
- sort(a.begin(), a.end(), &cmp);
- pt p1 = a[0], p2 = a.back();
- vector<int> up, down,p;
- up.push_back(p1.z);
- for (int i = 1; i < (int)a.size()-1; i++) {
- if (area(p1, a[i], p2)<0) {
- flag=2;
- }
- else if (area(p1, a[i], p2)>0) {
- down.push_back(a[i].z);
- flag=1;
- }
- }
- for (int i = 1; i < (a.size()-1); i++) {
- if (area(p1, a[i], p2)==0) {
- if(flag==2)down.push_back(a[i].z);
- else
- up.push_back(a[i].z);
- }
- else if (area(p1, a[i], p2)>0) {
- down.push_back(a[i].z);
- }
- else
- {
- up.push_back(a[i].z);
- }
- }
- down.push_back(p2.z);
- for (int i = 0; i < (int)a.size()-1; i++) {
- if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y)flag=0;
- }
- a.clear();
- for (int i = down.size() -1; i >=0; i--)
- up.push_back(down[i]);
- return up;
- }
- int main()
- {
- int i,j,k,t,n,x,y,z;
- cin>>t;
- z=t;
- while(t--)
- {
- cin>>n;
- flag=0;
- vector<pt>v;
- for(i=0;i<n;i++)
- {
- cin>>x>>y;
- v.push_back({x,y,i});
- }
- vector<int>p=convex_hull(v);
- cout<<"Case "<<z-t<<":\n";
- if(flag==0)
- { cout<<"Impossible"<<endl;
- continue;
- }
- for(i=0;i<n;i++)
- cout<<p[i]<<" ";
- cout<<endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment