Submission #3040971
Source Code Expand
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
double pi=3.14159265359; //円周率
double EPS = 1e-10; //誤差
class point
{
public:
double x,y;
int index;
point()
{x=0;y=0;index=0;}
//コンストラクタ
point(double a,double b)
{
x=a;y=b;index=0;
}
point(double a,double b,int i)
{
x=a;y=b;index=i;
}
//足し算
point operator + (point p)
{
return point(x+p.x,y+p.y);
}
//引き算
point operator - (point p)
{
return point(x-p.x,y-p.y);
}
//d倍
point operator * (double d)
{
return point(x*d,y*d);
}
//x座標昇順でソートする
bool operator < (const point &p)
const {
if(std::abs(x-p.x)>EPS)
return x<p.x;
else
return y<p.y;
}
//内積
//直交判定...abs(dot())<EPS
double dot(point p)
{
return x*p.x+y*p.y;
}
//外積
//平行判定...abs(cross())<EPS
double cross(point p)
{
return x*p.y-y*p.x;
}
//絶対値を求める
double abs()
{
return sqrt(x*x+y*y);
}
//単位ベクトルを求める
point ev()
{
return point(x/abs(),y/abs());
}
//単位法線ベクトル(の1つ)を求める
//もうひとつは-1倍することで求まる
point nev()
{
return point(-y/abs(),x/abs());
}
//2点間の距離を求める
//distがEPS未満なら2点は同じ位置にあるとみなす
double pdist(point p)
{
point v=point(p.x-x,p.y-y);
return v.abs();
}
//この点と直線p1-p2の距離を求める
double ldist(point p1,point p2)
{
return std::abs((p2.y-p1.y)*x-(p2.x-p1.x)*y+p2.x*p1.y+p2.y*p1.x)/(p2-p1).abs();
}
};
//線分p1-p2上に点qがあるか判定
bool on_seg(point p1,point p2,point q)
{
return abs((p1-q).cross(p2-q))<EPS && (p1-q).dot(p2-q)<=EPS;
}
//直線p1-p2と直線q1-q2の交点
//線分の交差判定はこれの戻り値が線分上にあるかどうかで判定する...on_seg(p1,p2,intersection(p1,p2,q1,q2))
point intersection(point p1,point p2,point q1,point q2)
{
return p1 + (p2-p1) * ((q2-q1).cross(q1-p1) / (q2-q1).cross(p2-p1));
}
//n頂点からなる多角形の面積を求める(vectorで頂点は与えられる)
double area(vector<point> p)
{
double ret=0;
for(int i=0;i<p.size()-1;i++)
{
ret+=p[i].cross(p[i+1]);
}
ret+=p[p.size()-1].cross(p[0]);
ret/=2;
return ret;
}
/*
3点a,b,cをa->b->cと進むとき、
* a->bで時計方向に折れてb->c (clockwise)
* a->bで反時計方向に折れてb->c(counter clockwise)
* a->bで逆を向いてaを通り越してb->c(c--a--b on line)
* a->bでそのままb->c(a--b--c on line)
* a->bで逆を向いてb->c(a--c--b on line)
のいずれのパターンかを判定する
*/
int ccw(point a,point b,point c)
{
b=b-a;c=c-a;
if(b.cross(c)>EPS)
return 1; //counter clockwise
if(b.cross(c)<-EPS)
return -1; //clockwise
if(b.dot(c)<-EPS)
return 2; //c--a--b on line
if(b.x*b.x+b.y*b.y < c.x*c.x+c.y*c.y)
return -2; //a--b--c on line
return 0; //a--c--b on line
}
//凸包を求める
vector<point> convex_hull(vector<point> p)
{
int n=p.size();
int k=0;
sort(p.begin(),p.end());
vector<point> ch(2*n);
//lower-hull 下側凸包
for(int i=0;i<n;ch[k++]=p[i++])
{
while(k>=2 && ccw(ch[k-2],ch[k-1],p[i])<=0)
k--;
}
//upper-hull 上側凸包
for(int i=n-2,t=k+1;i>=0;ch[k++]=p[i--])
{
while(k>=t && ccw(ch[k-2],ch[k-1],p[i])<=0)
k--;
}
ch.resize(k-1);
return ch;
}
vector<point> con;//凸法を求める
vector<point> p;//残っている点
point t[300];
bool tf[300];//残っている木を記録する
vector<tuple<int,int,int>> ans;
int main()
{
for(int i=0;i<300;i++)
{
double x,y;
cin>>x>>y;
t[i]=point(x,y,i+1);
p.push_back(t[i]);
tf[i]=true;
}
while(1)
{
con = convex_hull(p); //全体の凸包を求める
if(con.size()<3)
break;
//凸包から3つずつ区画を取る
for(int i=0;i+2<con.size();i+=3)
{
ans.push_back(make_tuple(con[i].index,con[i+1].index,con[i+2].index));
tf[con[i].index-1]=false;
tf[con[i].index-1]=false;
tf[con[i].index-1]=false;
}
//次のデータを入れる
p.clear();
for(int i=0;i<300;i++)
{
if(tf[i])
p.push_back(t[i]);
}
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++)
{
cout<<get<0>(ans[i])<<" "<<get<1>(ans[i])<<" "<<get<2>(ans[i])<<endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 役人 |
User |
Badlylucky |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4447 Byte |
Status |
WA |
Exec Time |
3 ms |
Memory |
256 KB |
Judge Result
Set Name |
Subtask00 |
Subtask01 |
Subtask02 |
Subtask03 |
Subtask04 |
Subtask05 |
Subtask06 |
Subtask07 |
Subtask08 |
Subtask09 |
Subtask10 |
Subtask11 |
Subtask12 |
Subtask13 |
Subtask14 |
Subtask15 |
Subtask16 |
Subtask17 |
Subtask18 |
Subtask19 |
Subtask20 |
Subtask21 |
Subtask22 |
Subtask23 |
Subtask24 |
Subtask25 |
Subtask26 |
Subtask27 |
Subtask28 |
Subtask29 |
Subtask30 |
Subtask31 |
Subtask32 |
Subtask33 |
Subtask34 |
Subtask35 |
Subtask36 |
Subtask37 |
Subtask38 |
Subtask39 |
Subtask40 |
Subtask41 |
Subtask42 |
Subtask43 |
Subtask44 |
Subtask45 |
Subtask46 |
Subtask47 |
Subtask48 |
Subtask49 |
Subtask50 |
Subtask51 |
Subtask52 |
Subtask53 |
Subtask54 |
Subtask55 |
Subtask56 |
Subtask57 |
Subtask58 |
Subtask59 |
Subtask60 |
Subtask61 |
Subtask62 |
Subtask63 |
Subtask64 |
Subtask65 |
Subtask66 |
Subtask67 |
Subtask68 |
Subtask69 |
Subtask70 |
Subtask71 |
Subtask72 |
Subtask73 |
Subtask74 |
Subtask75 |
Subtask76 |
Subtask77 |
Subtask78 |
Subtask79 |
Subtask80 |
Subtask81 |
Subtask82 |
Subtask83 |
Subtask84 |
Subtask85 |
Subtask86 |
Subtask87 |
Subtask88 |
Subtask89 |
Subtask90 |
Subtask91 |
Subtask92 |
Subtask93 |
Subtask94 |
Subtask95 |
Subtask96 |
Subtask97 |
Subtask98 |
Subtask99 |
Score / Max Score |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
0 / 1 |
Status |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
Subtask00 |
11_rand00.txt |
Subtask01 |
11_rand01.txt |
Subtask02 |
11_rand02.txt |
Subtask03 |
11_rand03.txt |
Subtask04 |
11_rand04.txt |
Subtask05 |
11_rand05.txt |
Subtask06 |
11_rand06.txt |
Subtask07 |
11_rand07.txt |
Subtask08 |
11_rand08.txt |
Subtask09 |
11_rand09.txt |
Subtask10 |
11_rand10.txt |
Subtask11 |
11_rand11.txt |
Subtask12 |
11_rand12.txt |
Subtask13 |
11_rand13.txt |
Subtask14 |
11_rand14.txt |
Subtask15 |
11_rand15.txt |
Subtask16 |
11_rand16.txt |
Subtask17 |
11_rand17.txt |
Subtask18 |
11_rand18.txt |
Subtask19 |
11_rand19.txt |
Subtask20 |
11_rand20.txt |
Subtask21 |
11_rand21.txt |
Subtask22 |
11_rand22.txt |
Subtask23 |
11_rand23.txt |
Subtask24 |
11_rand24.txt |
Subtask25 |
11_rand25.txt |
Subtask26 |
11_rand26.txt |
Subtask27 |
11_rand27.txt |
Subtask28 |
11_rand28.txt |
Subtask29 |
11_rand29.txt |
Subtask30 |
11_rand30.txt |
Subtask31 |
11_rand31.txt |
Subtask32 |
11_rand32.txt |
Subtask33 |
11_rand33.txt |
Subtask34 |
11_rand34.txt |
Subtask35 |
11_rand35.txt |
Subtask36 |
11_rand36.txt |
Subtask37 |
11_rand37.txt |
Subtask38 |
11_rand38.txt |
Subtask39 |
11_rand39.txt |
Subtask40 |
11_rand40.txt |
Subtask41 |
11_rand41.txt |
Subtask42 |
11_rand42.txt |
Subtask43 |
11_rand43.txt |
Subtask44 |
11_rand44.txt |
Subtask45 |
11_rand45.txt |
Subtask46 |
11_rand46.txt |
Subtask47 |
11_rand47.txt |
Subtask48 |
11_rand48.txt |
Subtask49 |
11_rand49.txt |
Subtask50 |
11_rand50.txt |
Subtask51 |
11_rand51.txt |
Subtask52 |
11_rand52.txt |
Subtask53 |
11_rand53.txt |
Subtask54 |
11_rand54.txt |
Subtask55 |
11_rand55.txt |
Subtask56 |
11_rand56.txt |
Subtask57 |
11_rand57.txt |
Subtask58 |
11_rand58.txt |
Subtask59 |
11_rand59.txt |
Subtask60 |
11_rand60.txt |
Subtask61 |
11_rand61.txt |
Subtask62 |
11_rand62.txt |
Subtask63 |
11_rand63.txt |
Subtask64 |
11_rand64.txt |
Subtask65 |
11_rand65.txt |
Subtask66 |
11_rand66.txt |
Subtask67 |
11_rand67.txt |
Subtask68 |
11_rand68.txt |
Subtask69 |
11_rand69.txt |
Subtask70 |
11_rand70.txt |
Subtask71 |
11_rand71.txt |
Subtask72 |
11_rand72.txt |
Subtask73 |
11_rand73.txt |
Subtask74 |
11_rand74.txt |
Subtask75 |
11_rand75.txt |
Subtask76 |
11_rand76.txt |
Subtask77 |
11_rand77.txt |
Subtask78 |
11_rand78.txt |
Subtask79 |
11_rand79.txt |
Subtask80 |
11_rand80.txt |
Subtask81 |
11_rand81.txt |
Subtask82 |
11_rand82.txt |
Subtask83 |
11_rand83.txt |
Subtask84 |
11_rand84.txt |
Subtask85 |
11_rand85.txt |
Subtask86 |
11_rand86.txt |
Subtask87 |
11_rand87.txt |
Subtask88 |
11_rand88.txt |
Subtask89 |
11_rand89.txt |
Subtask90 |
11_rand90.txt |
Subtask91 |
11_rand91.txt |
Subtask92 |
11_rand92.txt |
Subtask93 |
11_rand93.txt |
Subtask94 |
11_rand94.txt |
Subtask95 |
11_rand95.txt |
Subtask96 |
11_rand96.txt |
Subtask97 |
11_rand97.txt |
Subtask98 |
11_rand98.txt |
Subtask99 |
11_rand99.txt |
Case Name |
Status |
Exec Time |
Memory |
11_rand00.txt |
WA |
3 ms |
256 KB |
11_rand01.txt |
WA |
3 ms |
256 KB |
11_rand02.txt |
WA |
3 ms |
256 KB |
11_rand03.txt |
WA |
3 ms |
256 KB |
11_rand04.txt |
WA |
3 ms |
256 KB |
11_rand05.txt |
WA |
3 ms |
256 KB |
11_rand06.txt |
WA |
3 ms |
256 KB |
11_rand07.txt |
WA |
3 ms |
256 KB |
11_rand08.txt |
WA |
3 ms |
256 KB |
11_rand09.txt |
WA |
3 ms |
256 KB |
11_rand10.txt |
WA |
3 ms |
256 KB |
11_rand11.txt |
WA |
3 ms |
256 KB |
11_rand12.txt |
WA |
3 ms |
256 KB |
11_rand13.txt |
WA |
3 ms |
256 KB |
11_rand14.txt |
WA |
3 ms |
256 KB |
11_rand15.txt |
WA |
3 ms |
256 KB |
11_rand16.txt |
WA |
3 ms |
256 KB |
11_rand17.txt |
WA |
3 ms |
256 KB |
11_rand18.txt |
WA |
3 ms |
256 KB |
11_rand19.txt |
WA |
3 ms |
256 KB |
11_rand20.txt |
WA |
3 ms |
256 KB |
11_rand21.txt |
WA |
3 ms |
256 KB |
11_rand22.txt |
WA |
3 ms |
256 KB |
11_rand23.txt |
WA |
3 ms |
256 KB |
11_rand24.txt |
WA |
3 ms |
256 KB |
11_rand25.txt |
WA |
3 ms |
256 KB |
11_rand26.txt |
WA |
3 ms |
256 KB |
11_rand27.txt |
WA |
3 ms |
256 KB |
11_rand28.txt |
WA |
3 ms |
256 KB |
11_rand29.txt |
WA |
3 ms |
256 KB |
11_rand30.txt |
WA |
3 ms |
256 KB |
11_rand31.txt |
WA |
3 ms |
256 KB |
11_rand32.txt |
WA |
3 ms |
256 KB |
11_rand33.txt |
WA |
3 ms |
256 KB |
11_rand34.txt |
WA |
3 ms |
256 KB |
11_rand35.txt |
WA |
3 ms |
256 KB |
11_rand36.txt |
WA |
3 ms |
256 KB |
11_rand37.txt |
WA |
3 ms |
256 KB |
11_rand38.txt |
WA |
3 ms |
256 KB |
11_rand39.txt |
WA |
3 ms |
256 KB |
11_rand40.txt |
WA |
3 ms |
256 KB |
11_rand41.txt |
WA |
3 ms |
256 KB |
11_rand42.txt |
WA |
3 ms |
256 KB |
11_rand43.txt |
WA |
3 ms |
256 KB |
11_rand44.txt |
WA |
3 ms |
256 KB |
11_rand45.txt |
WA |
3 ms |
256 KB |
11_rand46.txt |
WA |
3 ms |
256 KB |
11_rand47.txt |
WA |
3 ms |
256 KB |
11_rand48.txt |
WA |
3 ms |
256 KB |
11_rand49.txt |
WA |
3 ms |
256 KB |
11_rand50.txt |
WA |
3 ms |
256 KB |
11_rand51.txt |
WA |
3 ms |
256 KB |
11_rand52.txt |
WA |
3 ms |
256 KB |
11_rand53.txt |
WA |
3 ms |
256 KB |
11_rand54.txt |
WA |
3 ms |
256 KB |
11_rand55.txt |
WA |
3 ms |
256 KB |
11_rand56.txt |
WA |
3 ms |
256 KB |
11_rand57.txt |
WA |
3 ms |
256 KB |
11_rand58.txt |
WA |
3 ms |
256 KB |
11_rand59.txt |
WA |
3 ms |
256 KB |
11_rand60.txt |
WA |
3 ms |
256 KB |
11_rand61.txt |
WA |
3 ms |
256 KB |
11_rand62.txt |
WA |
3 ms |
256 KB |
11_rand63.txt |
WA |
3 ms |
256 KB |
11_rand64.txt |
WA |
3 ms |
256 KB |
11_rand65.txt |
WA |
3 ms |
256 KB |
11_rand66.txt |
WA |
3 ms |
256 KB |
11_rand67.txt |
WA |
3 ms |
256 KB |
11_rand68.txt |
WA |
3 ms |
256 KB |
11_rand69.txt |
WA |
3 ms |
256 KB |
11_rand70.txt |
WA |
3 ms |
256 KB |
11_rand71.txt |
WA |
3 ms |
256 KB |
11_rand72.txt |
WA |
3 ms |
256 KB |
11_rand73.txt |
WA |
3 ms |
256 KB |
11_rand74.txt |
WA |
3 ms |
256 KB |
11_rand75.txt |
WA |
3 ms |
256 KB |
11_rand76.txt |
WA |
3 ms |
256 KB |
11_rand77.txt |
WA |
3 ms |
256 KB |
11_rand78.txt |
WA |
3 ms |
256 KB |
11_rand79.txt |
WA |
3 ms |
256 KB |
11_rand80.txt |
WA |
3 ms |
256 KB |
11_rand81.txt |
WA |
3 ms |
256 KB |
11_rand82.txt |
WA |
3 ms |
256 KB |
11_rand83.txt |
WA |
3 ms |
256 KB |
11_rand84.txt |
WA |
3 ms |
256 KB |
11_rand85.txt |
WA |
3 ms |
256 KB |
11_rand86.txt |
WA |
3 ms |
256 KB |
11_rand87.txt |
WA |
3 ms |
256 KB |
11_rand88.txt |
WA |
3 ms |
256 KB |
11_rand89.txt |
WA |
3 ms |
256 KB |
11_rand90.txt |
WA |
3 ms |
256 KB |
11_rand91.txt |
WA |
3 ms |
256 KB |
11_rand92.txt |
WA |
3 ms |
256 KB |
11_rand93.txt |
WA |
3 ms |
256 KB |
11_rand94.txt |
WA |
3 ms |
256 KB |
11_rand95.txt |
WA |
3 ms |
256 KB |
11_rand96.txt |
WA |
3 ms |
256 KB |
11_rand97.txt |
WA |
3 ms |
256 KB |
11_rand98.txt |
WA |
3 ms |
256 KB |
11_rand99.txt |
WA |
3 ms |
256 KB |